[Graph - DFS, Medium] Reorder Routes to Make All Paths Lead to the City Zero

https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/description/?envType=study-plan-v2&envId=leetcode-75

두 방향을 모두 담는 인접 리스트로 구현할 수 있다.
int[] {이웃 번호, 방향}

연결 리스트로 이어진 모든 이웃 노드를 순회 하면서, 방향에 따라 뒤집어야 할지 말지 계산해서 더함

• 이미 0쪽으로 향하고 있었으면 0
• 0에서 다른 쪽으로 이동이면 1

중복제거가 필요한데 visited해도 되고 아니면 next != parent 식으로 해도 된다

요약하자면
1. 인접 노드와 방향을 가지는 인접 리스트를 생성
2. 순회하면서 정방향이면 (0과 멀어지는 방향이면) 1씩 더함 -> 왜? 뒤집을 대상이니까
3. 방향에 따라 이미 값을 세팅했으므로 += direction 연산만 해주면 됨

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

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

        for (int[] edge : connections) {
            graph.get(edge[0]).add(new int[] {edge[1], 1});
            graph.get(edge[1]).add(new int[] {edge[0], 0});
        }

        return dfs(graph, 0, -1);
    }
    private int dfs(List<List<int[]>> graph, int current, int parent){
        int count = 0;
        for(int[] edge : graph.get(current)){
            int next = edge[0];
            int direction = edge[1];

            if(next != parent){
                count += direction + dfs(graph, next, current);
            }
        }
        return count;
    }
}