프로그래머스 - 순위(Java)

플로이드-와샬(Floyd-Warshall) 문제입니다.

플로이드 와샬은 모든 노드가 다른 노드로 갈 때의 가중치를 이차원 배열 형태로 저장하는 알고리즘입니다.

 

선수 n명과 대진표 일부가 주어졌을 때, 순위를 알 수 있는 선수의 수를 구하는 문제입니다.

플로이드 와샬은 기본적으로 돌아갈 경우가 더 짧으면 돌아가는 형태를 지닙니다.

// k를 거쳐서 가는 경우
for (int k = 1; k < n + 1; k++) {
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            if(dis[i][j] > dis[i][k] + dis[k][j]){
                ...
            }
        }
    }
}

 

이 말을 다르게 해석하면, 가중치가 갱신이 될 경우에는 연결된다라는 의미이기도 합니다.

즉 i가 k를 이기고, k가 j를 이긴다면 i는 j를 이기도록 갱신을 하면 됩니다.

 

이길 경우를 1로 두고, 지는 경우를 -1로 둬서 플로이드 와샬 이기고 지는 관계를 구현하면 됩니다.

세로축인 i를 기준으로 dis[i][j]의 값들이 전부 갱신이 된다면(0이 아니라면), 그 i는 순위를 매길 수 있게 됩니다.

 

[구현 코드]

class Solution {
    private static int[][] dis;
    public static int solution(int n, int[][] results) {

        dis = new int[n + 1][n + 1];

        for (int[] result : results) {
            int a = result[0];
            int b = result[1];
            
            // a는 b에게 이김
            dis[a][b] = 1;
            // b는 a에게 짐
            dis[b][a] = -1;
        }

        for (int k = 1; k < n + 1; k++) {
            for (int i = 1; i < n + 1; i++) {
                for (int j = 1; j < n + 1; j++) {
                    if (i == j) continue;
                    //i가 k를 이기고, k가 j를 이길때
                    if(dis[i][k]==1 && dis[k][j]==1){
                        dis[i][j] = 1;
                        dis[j][i] = -1;
                    }else if(dis[i][k]==-1 && dis[k][j]==-1){
                        dis[i][j] = -1;
                        dis[j][i] = 1;
                    }
                }
            }
        }

        int ans = 0;
        Loop1:for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if(i==j) continue;
                if (dis[i][j]==0) continue Loop1;
            }
            ans++;
        }

        return ans;
    }
}