99클럽 코테 스터디 23일차 TIL, 그래프(순위)

1. 문제 정의

2. 문제 접근

플로이드 와샬 알고리즘을 이용하여 노드의 관계를 통해 순위를 구하면 된다.

3. 문제 풀이

1. 그래프를 만든다.
2. 플로이드 와샬 알고리즘을 통해 각 노드의 순위를 구한다.
3. 각 노드마다 n-1개의 순위를 알고 있으면 정답을 더해준다.
4. 정답을 리턴한다.

4. 코드

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

        for (int[] e : results) {
            graph[e[0]][e[1]] = 1; //이겼을 경우 1로 초기화
            graph[e[1]][e[0]] = - 1; // 졌을 경우 -1로 초기화
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= n; k++) {
                    // i 가 j에게 이기는 경우
                    if(graph[i][k] == 1 && graph[k][j] == 1) {
                        graph[i][j] = 1;
                        graph[j][i] = -1;
                    }
                    // i 가 j 에게 지는 경우
                    if(graph[i][k] == -1 && graph[k][j] == -1) {
                        graph[i][j] = -1;
                        graph[j][i] = 1;
                    }
                }
            }
        }

        for(int i = 0 ; i <=n; i++) {
            int count = 0;
            for (int j = 0; j <= n; j++) {
                if(graph[i][j] != 0) count++; // 이기거나 지거나 둘 중에 하나의 결과값을 아는 경우
            }
            if(count == n-1) answer++; // n인 사람이 n-1의 결과를 알고 있으면 자신의 순위도 알 수 있음!
        }
        return answer;
    }
}

 

 

5. 회고

그래프 문제라고 해서 노드로 그래프는 그렸는데 풀이를 어떻게 해야 할지 감이 안잡혔다. 다른 사람들 풀이한걸 보니 플로이드 와샬 알고리즘이라는 것을 써서 대부분의 사람들이 문제를 해결했다. 내가 몰랐던 알고리즘을 봐서 신기했고, 다음에도 비슷한 문제가 나온다면 잘 활용해서 문제를 풀어야 겠다.