[LeetCode][DFS] Find Eventual 어쩌구 풀어보기

https://leetcode.com/problems/find-eventual-safe-states/submissions/2153038558/

Find Eventual Safe States - LeetCode

처음에는 terminal node를 가리키는 노드만 safe노드인줄 알았는데 terminal node를 가리키는 safe node를 가리키는 노드도 safenode였습니다.  

 

따라서 타고타고 가야하기 때문에 DFS를 하는 것이 옳아보입니다.

유향그래프이기 때문에 어제 보았던  union-find사용은 좀 어렵습니다.

 

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();

        terminalNode.resize(n, false);
        safeNode.resize(n, false);
        visitingNode.resize(n, false);
        unsafeNode.resize(n, false);

        for (int i = 0; i < n; ++i)
        {
            if (graph[i].empty())
            {
                terminalNode[i] = true;
                safeNode[i] = true;
            }
        }

        for (int i = 0; i < n; ++i)
        {
            if (!safeNode[i])
            {
                dfs(i, graph);
            }
        }

        vector<int> answer;

        for (int i = 0; i < n; ++i)
        {
            if (safeNode[i])
                answer.push_back(i);
        }

        return answer;
    }

    bool dfs(int cur, vector<vector<int>>& graph)
    {
        if (safeNode[cur])
            return true;

        if (unsafeNode[cur])
            return false;

        if (visitingNode[cur])
            return false;

        if (terminalNode[cur])
            return true;

        visitingNode[cur] = true;

        for (int next : graph[cur])
        {
            if (!dfs(next, graph))
            {
                visitingNode[cur] = false;
                unsafeNode[cur] = true;
                return false;
            }
        }

        visitingNode[cur] = false;
        safeNode[cur] = true;

        return true;
    }

public:
    vector<bool> terminalNode;
    vector<bool> safeNode;
    vector<bool> visitingNode;
    vector<bool> unsafeNode;
};

 

실행시간 단축을 위해 이미 safenode로 판별된 노드는 safenode로 기록해놓아 이후에 해당 node를 가리키는 다른 노드들이 빠르게 판단할 수 있도록 최적화 했습니다.

---

2번방법

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        state.resize(n, 0);

        vector<int> answer;

        for (int i = 0; i < n; ++i)
        {
            if (dfs(i, graph))
                answer.push_back(i);
        }

        return answer;
    }

    bool dfs(int cur, vector<vector<int>>& graph)
    {
        if (state[cur] == 1)
            return false;

        if (state[cur] == 2)
            return true;

        state[cur] = 1;

        for (int next : graph[cur])
        {
            if (!dfs(next, graph))
                return false;
        }

        state[cur] = 2;
        return true;
    }

private:
    vector<int> state;
};

state를 나눠 처리해 훨씬 간단한 코드가 되었습니다. 

bool 배열 여러개 사용하는 것은 int배열 하나를 사용하는 꼴이 되었네요 전체적인 논리의 깔은 비슷합니다.

0 = 아직 방문하지 않음
1 = 현재 DFS 경로에서 탐색 중
2 = cycle 없이 탐색 완료