[프로그래머스] 49191. 순위

문제 링크

[프로그래머스] 49191. 순위

풀이 과정

n 명의 선수들을 승패 기준으로 줄 세울 수 있느냐는 문제입니다.

문제의 입력 예시를 살펴보겠습니다.

• 4번 선수는 3번 선수를 이겼습니다.
• 4번 선수는 2번 선수를 이겼습니다.
• 3번 선수는 2번 선수를 이겼습니다.
• 1번 선수는 2번 선수를 이겼습니다.
• 2번 선수는 5번 선수를 이겼습니다.

그래프에서의 간선 방향은 이긴 사람으로부터 진 사람으로 나타냅니다.

위의 예시에서 2번 선수는 1, 3, 4번 선수로부터 졌고, 5번 선수를 이겼습니다. 총원 5명 중, 나머지 4명과의 경기를 치뤘으므로, 선수의 순위를 매길 수 있습니다.

이제 5번 선수를 기준으로 보겠습니다. 예시에서 5번 선수는 2번 선수와의 경기 결과만 주어졌지만, 2번 선수는 1, 3, 4번 선수와의 경기 결과, 모두 패배한 이력을 갖고 있으므로, 그런 2번 선수에게 진 5번 선수는 자동으로 꼴등이 됩니다.

A 선수가 B 선수에게 이기고, B 선수가 C 선수에게 이겼다면, A 선수는 C 선수에게도 이긴 것입니다. 정점 i, j가 존재할 때, i → j로, 혹은 j → i로의 경로 존재 유무는 곧, 두 선수간의 경기 결과를 확정지을 수 있다는 것을 의미하게 됩니다. 또한, 위에서 봤듯이 한 선수의 순위를 알기 위해선, 그 선수를 제외한 모든 선수와의 경기 이력이 있어야 합니다.

정점 i 에서 정점 k를 거쳐 정점 j로 도달할 수 있는 지, 이 여부를 플로이드-워셜 알고리즘을 통해 구현할 수 있습니다. 하지만, 이 문제에서 플로이드-워셜 알고리즘은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 데에 의미가 있는 것이 아니라, 단순히 시작 정점에서 다른 정점 하나를 거쳐 목적지 정점으로 갈 수 있느냐 판단을 위해 사용됩니다.

위 배열은 플로이드-워셜 적용 결과입니다. 5번 째 행(5번 선수)을 기준으로 살펴보면, 정점 5에서 뻗어 나가는 간선이 없기에(갈 수 없기에) 모든 요소가 INF로 채워진 것을 알 수 있습니다. 5번 째 열을 기준으로 살펴보면, 자기 자신을 제외한 나머지 정점들로부터의 진입이 가능하다는 점을 확인할 수 있습니다. 이는, 5번 선수는 다른 모든 선수와의 경기 결과로 순위를 매길 수 있음을 의미합니다.

코드

import java.util.Arrays;

public class Main {
    static final int INF = 987654321;

    public static int solution(int n, int[][] results) {
        int answer = 0;

        int[][] map = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++)
            Arrays.fill(map[i], INF);

        for (int i = 0; i < results.length; i++) {
            map[results[i][0]][results[i][1]] = 1;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (map[i][j] > map[i][k] + map[k][j])
                        map[i][j] = map[i][k] + map[k][j];
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                if (map[i][j] != INF || map[j][i] != INF) cnt++;
            }

            if (cnt == n - 1) answer++;
        }

        return answer;
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] results = {{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}};

        solution(n, results);
    }
}