[LeetCode 802] Find Eventual Safe States

802. Find Eventual Safe States

그래프의 안전한 정점(Safe Nodes) 을 구하는 문제이다. 이를 위해서 위상 정렬을 약간 응용해야하는 문제

📌 문제 개념

• 안전한 노드:
  → 사이클이 포함되지 않은 정점들
  → 즉, 어떠한 경로를 따라가도 끝에 반드시 도달하는 정점들.
  

📌 접근 방식

1. 주어진 그래프의 방향을 뒤집음 (즉, 역그래프 생성)

   • 원래의 간선이 A → B 라면, 역방향 간선 B → A로 저장
   • 이렇게 하면, outDegree 기반 위상 정렬 가능

       for(int i = 0 ; i < graph.size(); i++){
           outDegree[i] = graph[i].size();
           for(int j = 0 ; j<graph[i].size(); j++){
               outEdges[graph[i][j]].push_back(i);
           }
       }

2. 위상 정렬을 사용하여 안전한 노드 를 판별

   • outDegree가 0인 노드를 큐에 삽입 (사이클이 없는 끝 노드)
   • BFS로 진출 차수를 감소시키며 위상 정렬 수행
   • 최종적으로 남은 정점들은 안전한 정점이 됨

📌 정답

class Solution {
public:
    vector<int> topologySortedArr;
    vector<int> outDegree;
    vector<int> outEdges[10001];

    void topologySort() {
        queue<int> q;

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

        while(!q.empty()){
            int start = q.front();
            topologySortedArr.push_back(start);
            q.pop();

            for(auto next: outEdges[start]){
                outDegree[next]--;

                if(outDegree[next] == 0){
                    q.push(next);
                }
            }
        }
    }

    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        outDegree.resize(graph.size());
        
        for(int i = 0 ; i < graph.size(); i++){
            outDegree[i] = graph[i].size();
            for(int j = 0 ; j<graph[i].size(); j++){
                outEdges[graph[i][j]].push_back(i);
            }
        }

        topologySort();

        sort(topologySortedArr.begin(), topologySortedArr.end());

        return topologySortedArr;
    }
};