Rank

해당 문제는 여기에서 확인하실 수 있습니다.

이 문제는 주어진 권투 대회 결과를 바탕으로 각 선수가 다른 선수들과 비교 가능한지, 즉 순위를 정확히 매길 수 있는 선수가 몇 명인지 계산하는 문제입니다. 문제를 해결하는 핵심 아이디어는 "그래프에서의 승패 관계 전파"와 "정확한 순위 결정 가능 여부"를 판단하는 것입니다.

문제를 해결하기 위한 첫 번째 단계는 "경기 결과"를 어떻게 표현할 것인가입니다. 각 선수는 1번부터 n번까지 번호를 부여받고, 경기 결과는 두 선수 간의 승패 관계로 주어집니다. 이를 바탕으로 각 선수 간 승패 관계를 확실히 할 수 있는 방법을 찾아야 합니다. 문제를 그래프 모델로 접근하여 각 선수를 노드로 보고, 승패 관계를 방향 그래프로 표현합니다. 예를 들어, 경기 결과 [A, B]가 주어지면, A는 B를 이겼다는 의미이므로, 그래프에서 A -> B 간선이 존재한다고 할 수 있습니다. 이 관계를 저장하기 위해 2차원 배열 graph를 사용하여, graph ij가 1이면 i가 j를 이겼고, -1이면 i가 j에게 졌다고 나타내게 됩니다. 이 배열을 사용하여 두 선수 간의 직접적인 승패뿐 아니라, 간접적인 승패 관계도 추론할 수 있어야 합니다.

두 번째로, 주어진 경기 결과만으로는 일부 선수들 간의 승패 관계가 확실히 결정되지 않을 수 있습니다. 예를 들어, A가 B를 이기고, B가 C를 이겼다면, A와 C 사이의 승패 관계는 명확해집니다. 이런 승패 관계를 파악하기 위해 플로이드-워셜 알고리즘을 사용할 수 있습니다. 플로이드-워셜 알고리즘은 "모든 쌍의 최단 경로"를 구하는 알고리즘으로, 여기서는 선수 간의 승패 관계를 간접적으로 확립하는 데 사용됩니다. 이 알고리즘은 각 선수와 다른 선수들 간의 승패 관계를 전파하여, 중간 선수를 거쳐 승패를 추론할 수 있게 만듭니다. 즉, i가 k를 이기고, k가 j를 이기면, i는 j를 이겼다고 설정하는 방식으로 승패 관계를 업데이트합니다.

세 번째로, 정확한 순위를 매길 수 있는 선수는, 승패 관계가 확실히 정의된 선수들입니다. 각 선수에 대해, 그 선수와 승패가 확실히 결정된 다른 선수가 n-1명이라면, 그 선수는 정확히 순위를 매길 수 있습니다. 예를 들어, A 선수가 다른 선수들과의 승패 관계가 모두 확실하다면 A는 정확한 순위를 매길 수 있습니다. 이를 통해 모든 선수에 대해 승패 관계가 확실한 선수의 수를 세면 됩니다.

class Solution {
  public int solution(int n, int[][] results) {
    // 선수 간 승패 관계를 저장할 2D 배열
    int[][] graph = new int[n + 1][n + 1];
    
    // 자기 자신과의 관계는 0으로 설정 (승패 관계가 없으므로)
    for (int i = 1; i <= n; i++) {
      graph[i][i] = 0;
    }
    
    // 경기 결과에 따른 승패 관계 설정
    for (int[] result : results) {
      int winner = result[0];  // 승리한 선수
      int loser = result[1];   // 패배한 선수
      graph[winner][loser] = 1;  // winner가 loser를 이김
      graph[loser][winner] = -1; // loser가 winner에게 짐
    }
    
    // 플로이드-워셜 알고리즘으로 모든 선수 간의 승패 관계 전파
    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          // i가 k에게 이기고, k가 j에게 이기면 i는 j를 이긴다
          if (graph[i][k] == 1 && graph[k][j] == 1) {
            graph[i][j] = 1;
          }
          // i가 k에게 지고, k가 j에게 지면 i는 j에게 진다
          if (graph[i][k] == -1 && graph[k][j] == -1) {
            graph[i][j] = -1;
          }
        }
      }
    }

    int answer = 0;
    // 각 선수에 대해 정확한 순위를 매길 수 있는지 체크
    for (int i = 1; i <= n; i++) {
      int count = 0;
      for (int j = 1; j <= n; j++) {
        // i와 j의 승패 관계가 확실하면 count 증가
        if (graph[i][j] != 0) {
          count++;
        }
      }
      // 승패 관계가 확실한 선수가 n-1명이라면, 정확한 순위를 매길 수 있음
      if (count == n - 1) {
        answer++;
      }
    }

    return answer;  // 정확히 순위를 매길 수 있는 선수의 수 반환
  }
}