[프로그래머스] 순위

문제 주소

https://school.programmers.co.kr/learn/courses/30/lessons/49191

풀이 과정

플로이드-워셜 알고리즘

플로이드 워셜 알고리즘은 주어진 그래프의 모든 노드간의 최단 경로를 구하는 알고리즘이다.

플로이드 워셜 알고리즘은 노드마다 해당 노드를 거쳐가는 최단 거리를 계산한다. 즉, 각 노드 m마다 노드 s -> 노드 m -> 노드 e로 가는 거리를 계산해서 이것이 s에서 바로 e로 가는 거리보다 짧으면 갱신한다.

이를 코드로 나타내면 다음과 같다.

for(int m = 0; m < n; m++){
    for(int s = 0; s < n; s++){
        for(int e = 0; e < n; e++){
            if (d[s][e] > d[s][m] + d[m][e]) d[s][e] = d[s][m] + d[m][e];
        }
    }
}

중간 노드를 기준으로 순회해야 되는 이유
출발 노드를 기준으로 중간 노드와 도착 노드를 순회한다고 가정해보자.
a -> b -> c -> d가 a -> d 로 가는 최단 경로이고, a부터 순회한다고 하면 최단 경로가 하나의 노드를 경유하면서 a -> d로 가는 경우가 아니기 때문에 a -> d로 가는 최단거리를 계산하지 못한다.

반면 중간 노드를 기준으로 순회하는 경우, 예를 들어 c를 중간노드로 순회하는 경우 b -> c -> d가 b에서 d로 가는 최단 경로이므로 이때 b에서 d로 가는 최단 거리가 계산된다. b에서 d의 최단거리가 이미 저장되어 있으므로 a -> b -> c -> d 경로를 찾는 것은 a -> b -> d 경로를 찾는것과 같아진다.

즉, 중간노드를 순회하는 것은 최단경로에서 중간노드를 무시하는것과 같은 효과가 생긴다. 어떤 식으로 최단경로가 주어지더라도 중간노드를 하나씩 무시하다 보면 결국 a -> b -> c와 같은 형태로 귀결되기 때문에 모든 중간노드를 순회하면 최단거리를 구할 수 있게 된다.

풀이

승리를 표현하는 단방향 그래프와 패배를 표현하는 단방향 그래프를 각각 만들었다. 두 그래프가 합쳐져 있을 경우 결과가 [a, c], [b, c]와 같이 주어졌을 때 a와 b가 연결되게 되는데, 실제로는 둘사이의 승패를 알수 없으므로 문제가 생긴다.

본인의 순위가 확정되기 위해서는 다른 선수들과의 승패가 간접적으로라도 확정되어야 한다. 이를 다르게 표현하면, 승리 그래프에서 이동이 가능한 노드의 개수(상대했을 때 승리하게 되는 플레이어 수)와 패배 그래프에서 이동이 가능한 노드의 개수(상대했을 때 패배하게 되는 플레이어 수)를 더했을 때 자신을 제외한 총 플레이어 수가 나와야 한다.

각 노드간 최단거리를 구했을 때 기존에 설정한 최대값보다 거리가 작다면 이동할 수 있다는 의미가 된다. 따라서 이를 확인하기 위해 위 알고리즘을 사용해서 최단 거리를 구한다.

최종 코드

class Solution {
    public int solution(int n, int[][] results) {
        int[][] win = new int[n][n];
        int[][] lose = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                win[i][j] = 256;
                lose[i][j] = 256;
            }
        }
        for(int[] result : results){
            win[result[0] - 1][result[1] - 1] = 1;
            lose[result[1] - 1][result[0] - 1] = 1;
        }
        for(int m = 0; m < n; m++){
            for(int s = 0; s < n; s++){
                for(int e = 0; e < n; e++){
                    if (win[s][e] > win[s][m] + win[m][e]) win[s][e] = win[s][m] + win[m][e];
                    if (lose[s][e] > lose[s][m] + lose[m][e]) lose[s][e] = lose[s][m] + lose[m][e];
                }
            }
        }
        int count = 0;
        for(int i = 0; i < n; i++){
            int temp = 0;
            for(int j = 0; j < n; j++){
                if(win[i][j] <= n || lose[i][j] <= n) temp++;
            }
            if(temp + 1 == n) count++;
        }
        return count;
    }    
}