<Medium> Find Eventual Safe States (LeetCode : C#)

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

📕 문제 설명

노드 개수와 인접 리스트 정보가 주어질 때 모든 safe node들을 오름차순으로 정렬해서 반환

graph[i] = i번째 노드와 인접한 노드 정보

terminal node: 나가는 edge가 없는 노드
safe node: 해당 노드에서 시작되는 path가 모두 terminal node나 또 다른 safe node로 이어지는 노드 (즉, cycle이 없는 노드를 의미함)

• Input
  그래프 정보
• Output
  오름차순 정렬된 safe node들

예제

풀이

safe node 기록하는 배열 하나 두고 cycle 있는지 체크하면서 갱신해나가기 -> 한 노드에 대해 safe인거 확인되면 answer에 추가

public class Solution {
    public IList<int> EventualSafeNodes(int[][] graph) {
        int[] isSafeNode = new int[graph.Length];
        List<int> answer = new List<int>();
        bool[] visited = new bool[graph.Length];
        for (int i = 0; i < graph.Length; i++)
        {
            bool result = IsSafeNode(graph, isSafeNode, visited, i);
            if (result) answer.Add(i); // safe node면 answer에 추가
        }

        return answer;
    }

    public bool IsSafeNode(int[][] graph, int[] isSafeNode, bool[] visited, int currNode)
    {
        visited[currNode] = true;
        for (int i = 0; i < graph[currNode].Length; i++)
        {
            int adjNode = graph[currNode][i];
            if (isSafeNode[adjNode] == 1) continue;
            if (isSafeNode[adjNode] == -1 || visited[adjNode] || !IsSafeNode(graph, isSafeNode, visited, adjNode)) 
            {
                isSafeNode[currNode] = -1;
                return false; // cycle 있는 경우
            }
        }

        visited[currNode] = false;
        isSafeNode[currNode] = 1;
        return true;
    }
}

결과