Find Eventual Safe States

cyclic 그래프 문제를 한번 내가 알고 있는 지식 선에서 풀어봤다. 테스트 케이스를 다 통과하긴 했는데.. 너무 시간이 오래 걸렸어서 굉장히 찜찜하다.

이 문제는 단순하게 현재 그래프에서 싸이클이 생기면 끝나는게 아니라 현재 그래프에서 연결된 모든 그래프에서 싸이클이 하나라도 생기면 안된다.

근데 내가 처음 적은 코드의 경우 node를 전부 탐색하면서...만약에 싸이클이 발생할 경우 확인을 해준뒤에 DFS가 끝나고 돌아오는 부분에서 flag 값으로 싸이클을 확인해주었다.

심지어 나는 매번 탐색마다 조회 조건을 초기화 해줘서 아마 1000개의 노드가 있으면 ... 1000개의 노드만큼 더 탐색했을 것이다.

그 아래에 있는 코드의 경우 적절하게 싸이클이 발생했을경우 return 값을 넣어줘서 돌아오는 루프에서도 싸이클을 다 확인해주었다.

원래 사용되는 알고리즘은 topological sort 라고 하는데 솔직히 잘 몰라서 한번 좀 볼 생각이다.

class Solution {
bool flag = false; 
public: 
    void dfs(vector<int>& visited, vector<vector<int>>& adj, int node){
        visited[node]++; 
        for(int n : adj[node]){
            if(!visited[n]){
                dfs(visited,adj,n); 
            } else if (visited[n]){
                visited[n]++; 
                //return; 
                //cout << visited[node]; 
            }
        }
        if(visited[node] > 1) flag = true; 
    }
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> answer; 
        
        vector<vector<int>> adj(graph.size()); 
        for(int i = 0; i < graph.size(); i++){
            adj[i] = graph[i]; 
        }

        for(int i = 0; i < graph.size(); i++){
            vector<int> visited(graph.size(),0);  
            flag = false; 
            dfs(visited,adj,i);
            //if(visited[i] == 1) answer.push_back(i); 
            if(flag == false) answer.push_back(i); 
        }
        
        
        //if(dfs(visited,adj,0)) answer.push_back(0);

        //sort(answer.begin(),answer.end()); 
        return answer; 
    }
};

성능 개선

class Solution {
public: 
    bool dfs(vector<vector<int>>& graph, int node, vector<int>& visited){
        if(visited[node]){
            return visited[node] == 1; 
        }

        visited[node] = -1; 

        for(int n : graph[node]){
            if(!dfs(graph,n,visited)){
                return false; 
            }
        }

        visited[node] = 1; 

        return true; 
    }
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> visited(graph.size(),false); 
        vector<int> answer;  
        for(int i = 0; i < graph.size(); i++){
            if(dfs(graph,i,visited)){
                answer.push_back(i); 
            }
        }
        return answer; 
    }
};