[Leetcode] 802. Find Eventual Safe States

문제 요약

• 알고리즘 분류:  백트레킹, 수학, 배열
• 난이도: Medium
• 문제내용:
  • 개의 노드로 구성된 방향 그래프가 있으며, 각 노드는 0부터 n - 1까지 레이블이 지정되어 있습니다.
  • 그래프는 0-인덱스 기반의 2D 정수 배열 graph로 표현되는데, graph[i]는 노드 i에 인접한 노드들의 정수 배열입니다.
  • 터미널 노드(Terminal Node): 나가는 간선이 없는 노드입니다.
  • 안전 노드(Safe Node): 해당 노드에서 시작하는 모든 가능한 경로가 터미널 노드나 다른 안전 노드로 이어지는 노드입니다.
• 사이트 주소: 

문제풀이

이 문제는 얼핏 보면 복잡해 보이지만, 그래프 이론의 위상 정렬(Topological Sort)을 응용하여 해결할 수 있습니다. 여기서 주요 인사이트는 문제를 역방향으로 생각하는 것입니다. 위상정렬 관련 내용은 아래글로 확인해보면 된다.

https://jih3508.tistory.com/269

[알고리즘 이론] 위상 정렬(Topological Sorting)

접근 방법 

핵심 아이디어:

1. 그래프 뒤집기: 원래 그래프의 모든 간선 방향을 반대로 뒤집습니다.
2. 위상 정렬 활용: 뒤집힌 그래프에서 터미널 노드부터 시작하여 위상 정렬을 수행합니다.
3. 안전 노드 식별: 위상 정렬 결과에 포함된 노드들이 안전 노드입니다.

이런 접근 방식이 가능한 이유는 다음과 같습니다:

• 원래의 터미널 노드들은 뒤집힌 그래프에서 진입 차수(in-degree)가 0인 노드가 됩니다.
• 안전 노드들은 모든 경로가 터미널 노드로 이어지는 노드이므로, 뒤집힌 그래프에서는 터미널 노드들로부터 도달 가능한 노드들입니다.

1.그래프 뒤집기:

• 원래 그래프에서 노드 A에서 노드 B로 가는 간선이 있다면, 뒤집힌 그래프에서는 노드 B에서 노드 A로 가는 간선을 만듭니다.
• 뒤집힌 그래프에서 각 노드의 진입 차수를 계산합니다.

2.터미널 노드 식별:

• 원래 그래프에서 나가는 간선이 없는 노드(터미널 노드)를 찾아 큐에 넣습니다.

3.위상 정렬 수행:

• 큐에서 노드를 하나씩 꺼내어 결과 리스트에 추가합니다.
• 해당 노드와 연결된 노드들의 진입 차수를 1씩 감소시킵니다.
• 진입 차수가 0이 된 노드는 큐에 추가합니다.

4.결과 정렬:

• 결과 리스트를 오름차순으로 정렬합니다.

마무리

• 시간 복잡도: O(n + e) - 여기서 n은 노드의 수, e는 간선의 수입니다. 위상 정렬의 시간 복잡도는 O(n + e)이며, 결과 정렬에 O(n log n)이 추가됩니다.
• 공간 복잡도: O(n + e) - 뒤집힌 그래프를 저장하는 데 O(e), 진입 차수 배열과 결과 리스트에 O(n)의 공간이 필요합니다.

Code

Python

class Solution(object):
        def eventualSafeNodes(self, graph):
            size = len(graph)
            g = defaultdict(list)
            queue = deque([])
            ind = [0 for _ in range(size)]

            # 역방향 그래프 구성 및 진입 차수 계산
            for i in range(size):
                for node in graph[i]:
                    g[node].append(i) # 간선 방향 뒤집기
                    ind[i] += 1 # 진입 차수 증가
                if len(graph[i]) == 0: #  터미널 노드 식별
                    queue.append(i)

            result = []
            # 위상 정렬 수행
            while queue:
                node = queue.popleft()
                result.append(node)
                for next in g[node]:
                    ind[next] -= 1
                    if ind[next] == 0: # 진입 차수 감소 후 0이면 큐에 추가
                        queue.append(next)

            result.sort()
            return result

Java

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
            int n = graph.length;
            List<List<Integer>> g = new ArrayList<>();
            int[] ind = new int[n];
            Queue<Integer> q = new LinkedList<>();

            // 그래프 초기화
            for (int i = 0; i < n; i++) {
                g.add(new ArrayList<>());
            }

            // 역방향 그래프 구성 및 진입 차수 계산
            for (int i = 0; i < graph.length; i++) {
                int[] edges = graph[i];
                for (int e : edges) {
                    g.get(e).add(i);
                    ind[i]++;
                }
                if (edges.length == 0) {
                    q.offer(i);
                }
            }

            // 위상 정렬
            List<Integer> res = new ArrayList<>();
            while (!q.isEmpty()) {
                int node = q.poll();
                res.add(node);
                for (int nxt : g.get(node)) {
                    if (--ind[nxt] == 0) {  // 진입 차수 감소 후 0이면 큐에 추가
                        q.offer(nxt);
                    }
                }
            }

            // 결과 정렬
            Collections.sort(res);
            return res;
    }
}

Javascript

var eventualSafeNodes = function(graph) {
    const n = graph.length;
    const g = Array(n).fill().map(() => []);
    const ind = Array(n).fill(0);
    const queue = [];


    // 역방향 그래프 구성 및 진입 차수 계산
    for (let i = 0; i < graph.length; i++) {
        const edges = graph[i];
        for (let e of edges) {
            g[e].push(i);
            ind[i]++;
        }
        if (edges.length === 0) {
            queue.push(i);
        }
    }

    // 위상 정렬 수행
    const res = [];
    while (queue.length >0 ) {

        const node = queue.shift();
        res.push(node);
        for (let next of g[node]) {
            ind[next]--;
            if (ind[next] === 0) {
                queue.push(next);
            }
        }
    }

    // 결과 정렬
     res.sort((a, b) => a - b);
    return res;
};