[LeetCode] 802. Find Eventual Safe States

문제

방향 그래프에서 어떤 경로로 가든 결국 터미널 노드(나가는 간선 없음)에 도착하는 노드를 오름차순으로 반환한다.

핵심 아이디어

safe하지 않다는 것은 사이클에 빠질 수 있다는 뜻이다.

• 사이클 위에 있는 노드는 unsafe다.
• 사이클로 갈 수 있는 경로가 하나라도 있는 노드도 unsafe다.
• 나머지는 전부 safe다.

그래서 DFS로 사이클을 찾으면 되고, 노드 상태를 세 가지로 관리한다.

• 0 미방문
• 1 방문 중 (현재 DFS 경로 위에 있음) 또는 unsafe로 확정됨
• 2 safe로 확정됨

DFS 도중 상태가 1인 노드를 다시 만나면 사이클이다.

풀이

function eventualSafeNodes(graph: number[][]): number[] {
    const graphLen = graph.length;
    const state = Array(graphLen).fill(0);

    const isSafe = (n: number) => {
        if (state[n] > 0) return state[n] === 2;
        state[n] = 1;
        for (const neighbor of graph[n]) if (!isSafe(neighbor)) return false;
        state[n] = 2;
        return true;
    };

    const safeNodes = [];
    for (let i = 0; i < graphLen; i++) if (isSafe(i)) safeNodes.push(i);

    return safeNodes;
}

1. 처음 방문한 노드는 1로 표시하고 이웃을 탐색한다.
2. 이웃 중 하나라도 unsafe면 곧바로 false를 반환한다. 이때 노드는 1로 남아서 unsafe로 확정된다.
3. 이웃이 모두 safe면 2로 바꾼다.
4. 0부터 차례로 검사하므로 결과는 따로 정렬하지 않아도 오름차순이다.

1 하나가 "방문 중"과 "unsafe 확정"을 함께 표현한다는 점이 포인트다. 방문 중인 노드를 다시 만난 경우와 unsafe 노드를 만난 경우 모두 결과는 false이므로 구분할 필요가 없다.

삽질 기록

• 이웃이 터미널인지만 확인 → 0→1→2처럼 한 단계 건너 도착하는 노드를 놓친다. safe는 재귀적으로 정의된다.
• 탐색이 끝난 뒤에야 결과를 캐시 → 탐색 중인 노드에 표시가 없어서 사이클에서 무한 재귀에 빠진다.
• visited를 쌓기만 하고 빼지 않음 → 두 경로가 한 노드로 합류하는 다이아몬드 모양을 사이클로 오인한다.
• 시작 노드마다 새 visited로 탐색 → 결과를 재사용하지 못해 같은 노드를 반복 탐색하고 시간초과가 난다.

복잡도

• 시간 O(V + E): 모든 노드와 간선을 한 번씩만 본다.
• 공간 O(V): 상태 배열과 재귀 스택.