[프로그래머스 49191] 순위

• 출처: 프로그래머스 49191
• 분류: 그래프 · Lv.3

문제

선수 n명의 권투 경기 결과 results가 주어진다. A가 B를 이기면 항상 이긴다. 정확하게 순위를 매길 수 있는 선수의 수를 반환한다.

핵심

선수의 순위가 확정되려면 나머지 n-1명 모두와의 승패가 결정되어야 한다. A가 B를 이기고 B가 C를 이기면 A가 C를 이긴다 (전이). 각 선수에서 이긴 방향/진 방향으로 DFS하여 관계가 결정된 선수 수를 센다.

풀이

#include <vector>
using namespace std;

void dfs(int node, vector<vector<int>>& g, vector<bool>& visited) {
    visited[node] = true;
    for (int next : g[node]) {
        if (!visited[next]) dfs(next, g, visited);
    }
}

int solution(int n, vector<vector<int>> results) {
    vector<vector<int>> win(n + 1), lose(n + 1);
    for (auto& r : results) {
        win[r[0]].push_back(r[1]);   // r[0]이 이긴 상대
        lose[r[1]].push_back(r[0]);  // r[1]을 이긴 상대
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        vector<bool> v1(n + 1, false), v2(n + 1, false);
        dfs(i, win, v1);    // i가 이기는 선수들
        dfs(i, lose, v2);   // i를 이기는 선수들

        int known = 0;
        for (int j = 1; j <= n; j++) {
            if (j != i && (v1[j] || v2[j])) known++;
        }
        if (known == n - 1) answer++;
    }
    return answer;
}

메모

• 두 방향 DFS
  • win 그래프에서 DFS: i에서 도달 가능한 노드 = i가 (직접 또는 전이적으로) 이기는 선수들
  • lose 그래프(역방향)에서 DFS: i에서 도달 가능한 노드 = i를 이기는 선수들
  • 두 결과를 합쳐 관계가 결정된 선수 수를 구한다
• 순위 확정 조건
  • 선수 i의 순위가 확정되려면 나머지 n-1명 전원과 승패가 결정되어야 한다
  • v1[j](i가 j를 이김) 또는 v2[j](j가 i를 이김) 중 하나가 참이면 두 선수의 관계가 결정된 것이다
  • 이 개수가 정확히 n-1이면 순위가 확정된다
• Floyd-Warshall 대안
  • 모든 쌍의 도달 가능성을 O(N³)에 구하는 방법도 있다
  • 자세한 설명은 Floyd-Warshall 알고리즘 정리 참고

복잡도

풀이	시간	공간
DFS	O(N·(N+E))	O(N+E)
Floyd-Warshall	O(N³)	O(N²)