[LeetCode] 802. Find Eventual Safe States

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

leetcode - Find Eventual Safe States

문제 유형: dfs, 위상 정렬

문제 난이도: Medium

 

문제

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

 

n개의 노드로 이루어진 방향그래프가 있다. 0~n-1까지 라벨링이 되어있다.

2D배열로 인접리스트가 주어진다.

해당 노드에서 시작해서 모든 경로의 목적지가 터미널 노드, 즉 진출차수가 0인 노드에 도착한다면, 안전한 노드이다.

그래프의 모든 안전한 노드를 오름차순 정렬해서 반환하시오.

 

풀이

간선을 역으로 뒤집은 그래프를 만들어서, 진입차수가 0인 노드들부터 위상정렬을 하면서, 방문한 노드들은 모두 안전한 노드들이다.

배열에 담아둔다. 

위상 정렬은 사이클에서 중단되고, DAG인 서브그래프만 탐색하기에, 위상정렬을 탐색하면서의 노드들은 모두 안전하다.

 

dfs로도 문제를 해결할 수도 있지만, 여기서는 위상 정렬(Kahn's Algorithm)만 다룬다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> reversedGraph(n);
        vector<int> indegree(n, 0); //reversed Indegree.
        queue<int> q;

        for(int i = 0; i < n; ++i) {
            for(const auto &src : graph[i]) {
                reversedGraph[src].emplace_back(i);
                indegree[i]++;
            }
        }

        for(int i = 0; i < n; ++i) {
            if(indegree[i] == 0) q.push(i);
        }

        vector<int> ans;
        while(!q.empty()) {
            int curr = q.front();
            q.pop();
            ans.emplace_back(curr);

            for(const auto &next : reversedGraph[curr]) {
                indegree[next]--;
                if(indegree[next] == 0) q.push(next);
            }
        }

        sort(ans.begin(), ans.end());
        return ans;
    }
};