[Programmers] 순위

코딩테스트 연습 - 순위

---

[Floyd-Warshall]

플로이드 와샬 알고리즘을 수행해서, i번 사람이 j번 사람에게 직접/간접적으로 도달할 수 있는지 체크한 다음, i번 사람이 자기 자신을 제외한 모든 사람에게 도달할 수 있으면 순위를 확실히 알 수 있다.

 

문제에서 주어진 조건은 간선이 단방향이라는 것을 알려준다. 따라서 주어진 입력을 적절히 이용하여 직접적인 A와 B의 관계를 boolean[ ][ ]에 표현하고 플로이드 와샬을 수행하면, A가 C에게 도달 할 수 있는지 여부를 알 수 있다.

 

표를 보며 이해하면 더 쉽게 와닿을 수 있을 것이다.

 

주어진 입력으로 boolean[][] 배열을 지정하면 다음과 같다.

[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

F	T	F	F	F
F	F	F	F	T
F	T	F	F	F
F	T	T	F	F
F	F	F	F	F

(1, 2) = T로 표기되어 있는데, 이는 1과 2의 관계는 정해졌다는 뜻이다.

 

이제 플로이드 와샬을 사용하면 다음과 같다.

F	T	F	F	T
F	F	F	F	T
F	T	F	F	T
F	T	T	F	T
F	F	F	F	F

5번 행을 예로 설명하자면, (5, 1)은 F이지만, (1, 5)는 T이다. 따라서 1과 5는 관계가 정해졌다는 것이고,

(5, 2)는 F이지만 (2, 5)는 T이다. 이렇게 (i, j) 또는 (j, i) 둘 중 하나만 T여도 둘의 관계가 정해진 것이므로, 이 개수가 n-1개면 순위를 확실히 알 수 있는 사람의 개수를 증가시킨다.

# Code </>

class Solution {

    static boolean[][] dist = new boolean[101][101];

    public int solution(int n, int[][] results) {

        for(int[] arr:results)
            dist[arr[0]][arr[1]] = true;

        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    if(dist[i][k] && dist[k][j])
                        dist[i][j] = true;

        int answer = 0;
        
        for(int i=1; i<=n; i++) {
            int cnt = 0;
            
            for (int j = 1; j <= n; j++)
                if (dist[i][j] || dist[j][i])
                    cnt++;

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

        return answer;
    }
}