Solution.java

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        ArrayList<Integer>[] parent = new ArrayList[n];
        ArrayList<Integer>[] child = new ArrayList[n];
        
        for (int i = 0; i < n; i++) {
            parent[i] = new ArrayList<>();
            child[i] = new ArrayList<>();
        }
        
        for (int[] result : results) {
            parent[result[1] - 1].add(result[0] - 1);
            child[result[0] - 1].add(result[1] - 1);
        }
        
        for (int i = 0; i < n; i++) {
            boolean[] visited = new boolean[n];
            int p = dfs(i, parent, visited);
            int c = dfs(i, child, visited);
            
            if (p + c == n - 1) answer++;
        }
        
        return answer;
    }
    
    int dfs(int player, ArrayList<Integer>[] arr, boolean[] visited) {
        int num = 0;
        
        for (int i : arr[player]) {
            if (!visited[i]) {
                visited[i] = true;
                num++;
                num += dfs(i, arr, visited);
            }
        }
        
        return num;
    }
}

문제를 보고 위상정렬 알고리즘을 사용하여 풀면 되겠다는 생각이 들었지만

위상정렬 알고리즘이 생각나지않아 풀지 못했다..

위상정렬 알고리즘을 공부한 후 다시 도전해봐야겠다.

---

위상정렬 알고리즘 문제가 아니었다..

단순히 그래프를 탐색하는 문제였다.

플로이드-워셜 알고리즘을 사용해 풀어도되지만 나는 그냥 DFS 알고리즘을 이용하여 탐색했다.

DFS 대신 BFS를 사용해도 상관없을것 같다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges