Reorder Routes to Make All Paths Lead to the City Zero

분명히 쉬운 문제인데 푸는 방법을 잘못 선택해서 시간을 좀 날린 문제라고 생각한다. Directed 노드가 있을때 몇가지의 노드 노선을 변경시켜서 모든 노드가 0번째 노드로 향할 수 있게 만들면 되는 문제이다.

여기서 내가 Union Find 형식으로 답을 찾아내려고 해서 많이 시간을 낭비 했고 결론적으로는 Directed 가 아닌 Undirected 형식으로 생각하며 문제에 접근 해야 했다. 가상의 그래프를 만들어주고 만약 0으로 오는 그래프 노선이 아니라면은 answer 을 올려주는것으로 풀 수 있었다.

풀긴 했지만 찝찝하다..그래도 Union Find 에 대한 복습을 했다고 좋게 생각해야겠다.

class Solution {
    struct Node{
        int num,forEdge,backEdge; 
    };
    
public:
    void dfs(int node, vector<vector<Node>>& adj, vector<bool>& visited, int& answer){
        visited[node] = true; 
        for(Node& nodes : adj[node]){
            if(!visited[nodes.num]){
                visited[nodes.num] = true; 
                if(nodes.forEdge == 1) answer++; 
                dfs(nodes.num,adj,visited,answer); 
            }
        }
    }
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<Node>> adj(n); 
        vector<bool> visited(n,false); 
        int answer = 0; 
        for(vector<int>& v : connections){
            adj[v[0]].push_back({v[1],1,0}); 
            adj[v[1]].push_back({v[0],0,1}); 
        }
        
        dfs(0,adj,visited,answer); 
        
        return answer; 
    }
};

배운점:

1. DFS + 시뮬레이션
2. 포기하지 말자