[Java] leetcode 1466. 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/

Reorder Routes to Make All Paths Lead to the City Zero - LeetCode

풀이

풀이 알고리즘은 다음과 같다.

1. 주어진 방향 그래프를 정방향, 역방향으로 구현한다.
2. 정방향 탐색은 ans +=1 해준다.
3. 역방향 탐색은 그냥 진행한다.
4. ans 를 리턴한다.

 

문제에서 0이아닌 모든 정점은 정점 0 과 이어져있다 했음으로 단순히 정점 0 에서 dfs 탐색을 하였다.

코드

class Solution {
    int ans;
    ArrayList<ArrayList<Integer>> g;//in order
    ArrayList<ArrayList<Integer>> rg;//reverse graph
    public int minReorder(int n, int[][] connections) {
        g = new ArrayList<>();
        rg = new ArrayList<>();
        boolean[] v = new boolean[n];

        for(int i = 0 ;i < n ;i++){
            g.add(new ArrayList<>());
            rg.add(new ArrayList<>());
        }
        for(int x[] : connections){
            g.get(x[0]).add(x[1]);
            rg.get(x[1]).add(x[0]);         
        }
        v[0] = true;
        dfs(0, v);
        return ans;
    }
    public void dfs(int start,boolean[]v){        
        for(int nv : g.get(start)){
            if(!v[nv]){
                v[nv] = true;
                ans++;
                dfs(nv, v);
            }
        }
        for(int nv : rg.get(start)){
            if(!v[nv]){
                v[nv] = true;
                dfs(nv, v);
            }
        }
    }
}