[프로그래머스] (Java) 순위 (그래프) 문제풀이

 

 

📑 1. 문제설명

---

💡 2. 접근방식

• n명의 선수가 있을 때, 각 선수는 모든 다른 선수와 경기를 하여 n-1번의 승패를 기록한다.
• 즉, 전체 승패 결과만 있으면 각 선수의 상대적 위치를 정확히 판단해서 순위를 확정 할 수 있다. 

승패를 통해 순위를 결정하는 방법은 간단히 말하면 모든 선수들 간의 직접적인 경기 결과를 반영하는 것이다. 예를 들어, 선수 i와 선수 j가 경기를 하여 승패가 결정되면, 그 결과를 기록한다. 
 

플로이드 워셜(Floyd-Warshall) 알고리즘

모든 쌍 최단 경로(all-pairs shortest path)를 구하는 알고리즘으로 그래프의 모든 노드 쌍에 대해 가장 짧은 경로를 찾는 알고리즘이다. 이 알고리즘을 사용하면 그래프의 모든 노드에 대해 다른 모든 노드로 가는 최단 경로를 구할 수 있다. 

[JAVA] 플로이드-워셜 알고리즘

이 문제 해결을 위해 floyd[i][j] 2차원 배열을 사용하여 선수 간 승패를 나타내려고 한다.

 
처음에는 floyd[i][j] 배열을 초기화할 때는 모든 floyd[i][i]를 0으로 설정해 준다.

 
그리고 각 선수 간의 경기 결과에 따라 나머지 값들을 업데이트한다. n명의 선수가 있을 경우, floyd[i][j]는 n * n 크기의 2차원 배열이 된다. 하지만 0번인덱스는 안쓸것이기 때문에 실제 코드에서는 배열의 크기를 (n+1)*(n+1)로 선언했다

floyd[i][j]:

• floyd[i][j] = 1: i 선수가 j 선수를 이긴 경우
• floyd[i][j] = -1: i 선수가 j 선수에게 진 경우
• floyd[i][j] = 0 : i 선수와 j 선수가 동일한 선수인 경우 (즉, 자기 자신과의 경기는 승패를 나누지 않기 때문에 0)

이 때 반대 케이스도 알 수 있으므로 해당 값도 넣는다.
 
i 선수가 j 선수를 이겼다면, j 선수는 i선수에게 진 것이므로 아래 두 값을 채워넣을 수 있다.
floyd[i][j] = 1;
floyd[j][i] = -1;
 

가운데 0은 자기자신과 겨룬 경우이다.

 
이제 위의 정보를 이용하여 플로이드 워셜로 값이 0으로 된 부분들을 채워나간다. 

예를들어서 아래처럼 1 > 2 이고 2 > 5 이면 1 > 5 임을 알 수 있다.

if(floyd[1][2] == 1 && floyd[2][5] == 1) {
	floyd[1][5] = 1
	floyd[5][1] = -1
}

n명의 선수가 있을 때 각 선수의 순위를 확정 지으려면, 각 선수 별로 n-1승패를 알아야 한다. 

5명 이므로 각 행에 0이 아닌 값이 4개가 들어가야 한다. 

배열을 반복 순회 하면서 각 행에서 0이 아닌 값이 n-1개일 때 answer를 증가시킨다.

---

⭐ 3. 정답코드

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        // n+1 크기의 2차원 배열 선언 (0번 인덱스는 사용하지 않음)
        int[][] floyd = new int[n + 1][n + 1];

        // 게임 결과를 기반으로 승패 정보 입력
        for (int i = 0; i < results.length; i++) {
            int A = results[i][0];
            int B = results[i][1];
            
            // A가 B를 이긴 경우
            floyd[A][B] = 1;
            floyd[B][A] = -1;
        }
        
        // 플로이드 워셜 알고리즘을 사용하여 간접적인 승패 관계를 찾음
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= n; k++) {
                    // i가 k를 이기고, k가 j를 이기면 i가 j를 이긴다고 확정
                    if (floyd[i][k] == 1 && floyd[k][j] == 1) {
                        floyd[i][j] = 1;
                        floyd[j][i] = -1;
                    }
                    // i가 k에게 졌고, k가 j에게 졌으면 i가 j에게 진다고 확정
                    else if (floyd[i][k] == -1 && floyd[k][j] == -1) {
                        floyd[i][j] = -1;
                        floyd[j][i] = 1;
                    }
                }
            }
        }

        // 각 선수에 대해, 다른 선수들과의 승패 결과가 모두 확정되었는지 확인
        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            for (int j = 1; j <= n; j++) {
                if (floyd[i][j] != 0) {
                    cnt++;
                }
            }
            // n-1명과 승패가 확정되었다면, 순위를 확정할 수 있는 선수
            if (cnt == n - 1) {
                answer++;
            }
        }

        return answer;  // 순위를 확정할 수 있는 선수의 수를 반환
    }
}

 

👏🏻 좋아요 가장 많이 받은 코드

다들 비슷하게 푼 것 같다

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

        boolean[][] chk = new boolean[n + 1][n + 1];

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

        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 && chk[i][k] && chk[k][j]) {
                        chk[i][j] = true;
                    }
                }
            }
        }

        for(int i = 1; i < n + 1; i++) {
            boolean pass = true;
            for(int j = 1; j < n + 1; j++) {
                if(i != j && !(chk[i][j] || chk[j][i])) {
                    pass = false;
                    break;
                }
            }
            if(pass) {
                answer++;
            }
        }

        return answer;
    }
}

---

🐦 4. 같은 유형 문제 (그래프)

[프로그래머스] (Java) 가장 먼 노드 (그래프) 문제풀이