프로그래머스 Lv.3 순위 [Java]

1. 문제 링크

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

2. 문제 해설

순위를 확정 짓는 방법은 생각해내기 쉽다. 자신과 연관된 results 값이 n-1 개면 순위는 확정된다. (이때 n은 총 선수의 수)
문제에서 나온 경우로 예를 들자면, 2번 선수와 관련된 results 값은 [4, 3], [4, 2], [3, 2], [1, 2], [2, 5]이다. 즉, 1, 3, 4번 선수에게는 패했고, 5번 선수에게는 이긴 것이다. 자신과 관련된 경기 결과가 4개이므로 순위가 확정되었다. 2번 선수의 경우는 처리하기 쉽지만, 여기서 문제는 5번 선수와 같은 경우를 어떻게 처리할 것인가이다. 5번 선수는 주어진 results 값에서 자신과 연관된 값은 [2, 5] 밖에 없다. 하지만 1, 3, 4번에게 모두 진 2번에게 졌으므로 5번은 1, 2, 3, 4 모두에게 졌다는 것을 알 수 있다. 이것을 어떻게 처리해야할까?
플로이드-와샬 알고리즘의 접근 방식을 떠올려 보자. 플로이드-와샬 알고리즘은 모든 정점을 거쳐가면서 최단거리를 갱신하는 방식이다. 이와 같은 방식을 이용하여 본 문제에서는 i가 j를 이겼고, j가 k를 이겼다면 i는 k를 이겼다고 처리할 수 있다. (아래 코드에서 12~20줄)

3. 코드 보기

class Solution { 
    public int solution(int n, int[][] results) {
        boolean[][] game = new boolean[n][n];
        int answer = 0;
 
        for (int i = 0; i < results.length; i++) {
            int winner = results[i][0] - 1;
            int loser = results[i][1] - 1;
            game[winner][loser] = true;
        }
 
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                for (int k = 0; k < n; k++) {
                    if (game[i][j] && game[j][k]) {
                        game[i][k] = true;
                    }
                }
            }
        }
 
        for (int i = 0; i < n; i++) { // 자신과 연관된 결과의 수를 찾는 과정
            int winOrLose = 0;
 
            for (int j = 0; j < n; j++) {
                if (game[i][j] || game[j][i]) {
                    winOrLose++;
                }
            }
 
            if (winOrLose == n - 1) {
                answer++;
            }
        }
 
        return answer;
    }
}