프로그래머스 | 순위 - java

프로그래머스

 

# 핵심

플로이드 와샬 알고리즘?

 

개 어렵다. 혼자 못풀었다. 솔직히 남의 코드 보고 거의 베꼈다

(참고) https://gom20.tistory.com/178

 

 

<플로이드 와샬 알고리즘>

-> 직접적으로 연결된 노드가 아니더라도, K번 노드를 통해 간접적으로 연결될 수도 있다!

아래 왼쪽 짤에서도, 5번 노드는 2번 노드와만 직접적으로 연결되어 있지만, 2번 노드를 거쳐서 1번 노드와 3번 노드로도 이동할 수 있다.

오른쪽 짤에서도 2번 노드는 4번 노드와 직접 연결되어있지 않지만, 3번 노드를 거쳐간다면 4번 노드로 이동할 수 있게 된다.

[2번 노드를 거쳐가는 경우] (1) 5 < 2, 2 < 1 이라면 5 < 1 이다 (2) 5 < 2, 2 < 3 이라면 5 < 3 이다 (3) 1 < 2, 2 > 5 이라면 아무것도 안된다 등등등...

[3번 노드를 거쳐가는 경우] (1) 2 < 3, 3 < 4 이라면 3 < 4 이다 ....

 

즉, \

출발 노드 < 경유 노드, 경유 노드 < 도착 노드 인 경우 = 출발 노드 < 도착 노드

출발 노드 > 경유 노드, 경유 노드 > 도착 노드 인 경우 = 출발 노드 > 도착 노드

 

출발 노드와 도착 노드가 직접 대결을 하지 않았더라도 간접적으로 둘 간의 결과를 알아낼 수 있다.

 

플로이드 와살 알고리즘은 보통 다익스트라 알고리즘과 함께 최단거리 계산에 사용되는 대표적인 알고리즘이지만, 본 문제에서는 최단거리 계산의 용도가 아니라 응용 버전이다..

 

플로이드 와샬에 대해 더 알고싶으면 아래의 유튜브를 참고하자.. 이분의 영상이 참 도움이 됐다.

https://www.youtube.com/watch?v=9574GHxCbKc 

 

# 통과 코드

class Solution {

    public int solution(int n, int[][] results) {
        int[][] adj = new int[n][n];

        for (int[] result : results) {
            // 양방향 연결
            adj[result[1] - 1][result[0] - 1] = 1; // 승
            adj[result[0] - 1][result[1] - 1] = -1; // 패
        }

        for(int k = 0; k < n; k++) { // k번 노드를 거쳐가는 경우
            for(int i = 0; i < n; i++) { // 출발 노드
                for(int j = 0; j < n; j++) { // 도착 노드
                    // i > k && k > j ==> i > j
                    if(adj[i][k] == 1 && adj[k][j] == 1) {
                        adj[i][j] = 1; // 출발 노드 승
                        adj[j][i] = -1; // 도착 노드 패
                    }
                    // i < k && k < j ==> i < j
                    if(adj[i][k] == -1 && adj[k][j] == -1) {
                        adj[i][j] = -1; // 출발 노드 패
                        adj[j][i] = 1; // 도착 노드 승
                    }
                }
            }
        }

        int cnt = 0;
        for (int[] ints : adj) {
            int tmp = 0;
            // 해당 노드와 간접/직접적으로 연결된 노드가 n - 1개라면 순위를 확정할 수 있다.
            // * n - 1인 이유 = 본인 제외
            for (int anInt : ints) {
                if(anInt != 0) tmp++;
            }
            if(tmp == n - 1) cnt++;
        }
        return cnt;
    }
}

 

 

어떻게 이런 생각을 잘 할 수 있을까

진짜 아직도 부족한게 너무 많구나 다시한번 느끼고 간다..