순위

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

 

입출력 예

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

---

 

문제 설명

권투 경기가 1대 1방식으로 진행되고, 제공되는 배열이 경기 결과를 담은 2차원 배열이다. 여기서 그래프 임을 예상할 수 있다. 그래프는, 노드와 노드가 연결되는 간선 1개로 정의되는것 을 의미하기 때문이다.

 

정의방식 중, 1대 1방식으로 진행되고, A선수가 B선수보다 실력이 좋다면 A는 B를 항상 이김으로, A -> B를 이겼을 때, C가 A를 이긴다면, C -> A ->B 순으로 파워벨런스가 나뉘어짐을 의미한다.

 

정확하게 순위를 매길 수 있는 선수의 수를 return하라. 정확하게 순위를 매길 수 있다는 걸 기준으로 잡자.

정확하게 순위를 매길려면 해당 선수가 모든 선수와의 경기를 진행했다는 증거가 필요하다. 그럼으로 해당 선수가 다른 모든 선수와 지거나 이겼다, 또는 파워벨런스 체크가 가능하다고 이해하자.

 

그렇기 때문에, 각 승리와 패배에 따른 단방향 노드로 이루어진 그래프를 각각 생성하고, 순회한 다음. 순회결과를 서로 더해주면. 지정한 선수가 경기를 어떻게 했는지, 그리고 지정한 선수와 경기한 선수가 어떤 선수와 경기를 했는지 결과를 알 수 있다.

 

쉽게 이해하면,  C를 탐색하면 C -> A 로 승리 그래프가 이어지고, A에서 다시 B가 이어짐으로 A -> B임을 알 수 있기 때문에, C는 모든 선수와 파워벨런스를 맞추었음을 알 수 있다.

그러나, A를 탐색하면, A -> B임으로, A는, 한테 이기고 B 는 아무것도 안했음으로, 승리 만으로는 A가 B를 이긴다는 사실만 알고, C의 결과를 알 수 없다. 그럼으로 파워밸런스를 맞추지 못했다고 할 수 있다.

 

정리해보자. 제공받은 데이터로는 각 선수간 승리와 패배에 대한 그래프를 그릴 수 있음을 알 수 있다. 그리고, 항상 승리는 승리로, 패배는 패배로 이어지게 됨으로. 단방향 그래프 임을 이해할 수 있다.

 

이 그래프를 기준으로 이김과 짐을 전부 더하게 되면 결과물은 각각 자기자신 을 더하게 됨으로, 전체 선수 수 + 2 값이 나와야 모든 선수와의 승리여부 판명이 가능하다는 의미 일 것 이다.

---

첫 시도

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
 
using namespace std;

void dfs(int node, vector<vector<int>>& lineResult, vector<int>& visited) {
    visited[node] = 1;

    for (int neighbor : lineResult[node]) {
        if (visited[neighbor] != 1) {
            dfs(neighbor, lineResult, visited);
        }
    }
}

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<int>> wineResult;
    vector<vector<int>> loseResult;
    wineResult.resize(n);
    loseResult.resize(n);
    
    for(auto& leager : results)
    {
        wineResult[leager[0]-1].push_back(leager[1]-1);
        loseResult[leager[1]-1].push_back(leager[0]-1);
    }

    for (int i = 0; i < n; ++i) {
        vector<int> winVisited(n);
        vector<int> loseVisited(n);

        dfs(i, wineResult, winVisited);
        dfs(i, loseResult, loseVisited);

        int winCount = accumulate(winVisited.begin(), winVisited.end(), 0);
        int loseCount = accumulate(loseVisited.begin(), loseVisited.end(), 0);

        if (winCount + loseCount == n + 1) {
            answer++;
        }
    }
   
    return answer;
}

성공

 

DFS방식을 사용해서 순회하면 된다. 여기서 중요한 점은, 쌍방향 node순회가 아니라, 각각 이긴것과 진것 기준으로 단방향 순회를 전부 진행하고.

 

각 진행순환을 기준으로, 두개를 더해서 순회마다 각 자기자신을 포함하게 됨으로, n이 전체값의 +1 임으로 거기에 +1 하여 전체수 + 2만큼을 기준으로, count가 만족하는지 확인하고, 만족한다면, answer에 1을 더해준다.

 

이걸 전체 개수만큼 반복하면 현재 만족하는 객체가 몃개 있는지 확인할 수 있다.