Leet code (Medium) : 1466. Reorder Routes to Make All Paths Lead to the City Zero (DFS) - JAVA

 

방향성이 있는 그래프에서 진입차수 배열에 주어진 방향의 반대방향도 넣어두는 것이 포인트이다.

다만 이 반대방향이 주어진 방향을 뒤집은 방향이라는 것을 알게 하기 위해 음수로 저장했다.

 

class Solution {
    public int minReorder(int n, int[][] connections) {
        List<List<Integer>> al = new ArrayList<>();
        boolean[] visited = new boolean[n];

        for(int i = 0; i < n; i++){
            al.add(new ArrayList<>());
        }

        // 한 방향에 대해서 양방향으로 저장함.
        // 이때, 시작점에서 나가는건 양수, 반대는 음수로 저장.
        // => 여기선 시작점인 0 부터 차차 탐색하기 때문에, 간선방향이 모두 시작점으로 들어오는 방향이어야 정답이됨.
        for(int[] c : connections){
            al.get(c[0]).add(c[1]);
            al.get(c[1]).add(-c[0]);
        }

        return dfs(al, visited, 0);
    }

    public int dfs(List<List<Integer>> al, boolean[] visited, int from){
        int change = 0;
        visited[from] = true;
        for(int to : al.get(from)){
            if(!visited[Math.abs(to)]){
                // 시작점에서 나가는 방향인 간선일 경우. (방향이 바뀌어야함)
                if(to > 0){
                    change++;
                }
                
                change += dfs(al, visited, Math.abs(to));
            }
        }

        return change;
    }
}