[Leetcode] 1466. Reorder Routes to Make All Paths Lead to the City Zero

1.문제링크

https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city

각 동그라미와 숫자는 도시번호인데

각 도시가 모두 0으로 연결되도록 하려면 화살표를 최소 몇개 바꿔야하는지 그 최소개수를 return하는것이 문제이다.

 

 

 

2. 키포인트

자료구조 : Graph

알고리즘 : dfs

 

vector<vector<pair<int,int>>> adj(n)

우선 각 도시에서 input, output 화살표로 모두 연결되는 도시를 adj에 기록한다

output 화살표 방향은 1, input 화살표 방향은 -1으로 기록한다.

 

그럼 adj는

 

0 : [1,1] [4,-1] 
1 : [0,-1] [3,1] 
2 : [3,1] 
3 : [1,-1] [2,-1] 
4 : [0,1] [5,1] 
5 : [4,-1] 

 

위와 같이 표시할 수 있는데

우리는 모든 도시가 0으로 연결되게 하면 되기 때문에

dfs를 root부터 시작하게 한다.

 

city 가 root (0)일 때, 첫번째 pair가 화살표가 반대로 되어있다.

root와 연결되는 city는 1, 4인데 여기서 city 1이 화살표 방향이 반대이다

 

도시를 방문한 적이 없는 경우만!

 1) 화살표 방향이 반대라면 방향을 꿔주고 (change++)

 2) 각 도시를 방문해준다

 

한 번 방문한 도시는 다시 방문하지 않기 때문에 vector값을 변경할 필요는 없다

 

 

3. solution

    class Solution {
    public:
        void dfs(vector<vector<pair<int,int>>> &adj, vector<bool> &visit, int &change, int city){
            visit[city] = true;
            for(auto neighbor : adj[city]){
                if(!visit[neighbor.first]){
                    if(neighbor.second == 1)
                        change++;
                    dfs(adj, visit, change, neighbor.first);
                }
            }
        }
        int minReorder(int n, vector<vector<int>>& con) {
            vector<vector<pair<int,int>>> adj(n);
            vector<bool> visit(n);
            for(auto i : con){
                adj[i[0]].push_back({i[1], 1});
                adj[i[1]].push_back({i[0], -1});
            }
            // for(int i = 0; i < n; i++){
            //     cout << i << " : ";
            //     for(auto j : adj[i]){
            //         cout << "["<<j.first<<","<<j.second<<"] ";
            //     }cout<<endl;
            // }
            int change = 0;
            dfs(adj, visit, change, 0);
            return change;
        }
    };