[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

Reorder Routes to Make All Paths Lead to the City Zero

 

번호가 적힌 도시들이 있다. 이 도시들을 연결하는 길은 도시 하나당 다른 도시로 최대 한개의 길만 존재하고, 반대로 돌아오는 길은 존재하지 않는다. 이 때, 모든 도시에서 0번 도시로 돌아오려면 최소한 몇 개의 길의 방향을 바꿔야하는지 구하는 문제다.

 

처음에 모든 길을 무지향과 지향 둘다로 저장한다.

즉 connection[i]가 [0,1] 일 경우,

vector<int> G[]를 만들고, set<pair<int, int>> direction을 만들어

G[0] 에 1을 추가하고,

G[1] 에도 0을 추가해준다.

마지막으로 본래 방향인 (0->1)을 direction에 추가해준다.

 

그 다음 0번 도시부터 G를 이용해 dfs를 해주자.

dfs시에는 현재 도시(cur)와 target 도시를 인자로 받는다.

target은 0번 도시를 향하는 도시가 될 것이다

 

처음에 direction에 우리가 원하는 방향인 (cur->target)이 아닌 (target->cur) 가 direction에 존재하는지 체크한다.

존재할 경우, 이는 바꿔줘야 하므로 ret을 ++ 해준다.

이로써 target->cur 가 cur->target이 되어 cur도 0을 향하게 된다.

그 후, G[cur] 를 훑어 target을 제외하여 dfs(cur와 연결된도시, cur) 를 진행해주면 된다.

 

전체 풀이 코드

class Solution {
public:
    vector<int> G[50005];
    int ret = 0;
    set<pair<int, int>> direction;
    int minReorder(int n, vector<vector<int>>& connections) {
        for (auto connection:connections) {
            this->direction.insert(make_pair(connection[0],connection[1]));
            this->G[connection[0]].push_back(connection[1]);
            this->G[connection[1]].push_back(connection[0]);
        }
        run(0,0);
        return this->ret;
    }
    void run(int cur, int target) {
        if (this->direction.find(make_pair(target, cur))!=direction.end()) this->ret++;
        for (int i:this->G[cur]) if(i!=target) run(i, cur);
    }
};