[프로그래머스]순위(Java)

문제

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

풀이

DFS를 이용해 풀었다.
정확하게 순위를 매기기 위해서는 모든 사람들과 우위를 가릴 수 있어야 한다.
여기서, 굳이 직접 경기를 하지 않아도 우위를 가릴 수 있다.

예를 들어서, 4번 선수가 2번 선수를 이기고, 2번 선수가 5번 선수를 이긴다고 가정할 때, 4번 선수가 2번 선수를 이겼기 때문에 2번 선수보다 실력이 낮은 5번 선수 또한 이길 수 있다.

즉, DFS를 통해 직접 경기를 하지 않아도 각 선수 간의 경기 결과를 예측 할 수 있다.
이 것은 특정 선수보다 뛰어난 선수의 수를 구할 때와 뛰어나지 않은 선수의 수를 구할 때 둘 다 해당이 된다.

그러므로, 각 선수마다 DFS를 이용해 자기보다 뛰어난 선수의 수와 뛰어나지 않은 선수의 수를 구하고
이 둘의 합이 n-1이면 순위를 매길 수 있다.
(n-1인 이유는 자기 자신을 뺀 나머지 총 선수의 인원이다.)

코드

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

        boolean[][] adj = new boolean[n+1][n+1];
        for(int[] result : results){
            adj[result[0]][result[1]] = true;
        }
        for(int i=1;i<=n;i++){
            int win = searchWin(n, adj, i, new boolean[n+1]);
            int lose = searchLose(n, adj, i, new boolean[n+1]);
            if(win + lose == n-1) answer++;
        }
        return answer;
    }
    public int searchWin(int n, boolean[][] adj, int start, boolean[] visited){
        int sum = 0;
        for(int i=1;i<=n;i++){
            if(visited[i]) continue;
            if(adj[start][i]){
                visited[i] = true;
                sum += 1+searchWin(n, adj, i, visited);   
            }
        }
        return sum;
    }
    public int searchLose(int n, boolean[][] adj, int start, boolean[] visited){
        int sum = 0;
        
        for(int i=1;i<=n;i++){
            if(visited[i]) continue;
            if(adj[i][start]){
                visited[i] = true;
                sum += 1+searchLose(n, adj, i, visited);   
            }
        }
        return sum;
    }
}```