[LeetCode] 802. Find Eventual Safe States (해석, kotlin 풀이)

문제

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

각 노드의 라벨이 0부터 n-1까지 붙어있는 n개의 노드로 이루어진 방향 그래프가 있다. 그래프는 0-indexed 인 이차원 정수 배열 `graph`로 표현되고, graph[i]는 노드 i와 인접한 정수 배열이다. 즉, 노드 i로부터 grape[i]에 있는 노드들 간에는 간선이 존재한다.

 

만약 한 노드에서 나가는 간선이 없다면 해당 노드는 terminal node이다. 한 노드가 safe node라는 것은 해당 노드로부터 시작하는 모든 가능한 경로가 terminal node 혹은 다른 safe node로 이어진다는 것이다.

 

그래프의 모든 safe node를 포함하는 배열을 반환하여라. 배열은 오름차순으로 정렬되어야 한다.

 

풀이

DFS를 활용한 노드 탐색

fun eventualSafeNodes(graph: Array<IntArray>): List<Int> {
    val n = graph.size
    val result = mutableListOf<Int>()
    val visited = BooleanArray(n)
    val safe = BooleanArray(n)

    for(i in 0 until n) {
        if(dfs(i, visited, safe, graph)) {
            result.add(i)
        }
    }

    return result
}

private fun dfs(node: Int, visited: BooleanArray, safe:BooleanArray, graph: Array<IntArray>): Boolean {
    if(visited[node]) return safe[node]

    visited[node] = true

    graph[node].forEach {i ->
        if(!dfs(i, visited, safe, graph)) {
            return false
        }
    }

    safe[node] = true
    return true
}

visited: 해당 노드를 탐색하였는지 여부

safe: 해당 노드가 safe node인지 여부

 

DFS method

 - 해당 노드를 이미 방문하였다면 해당 노드의 safe node 여부를 반환 

 - graph[node]를 탐색하면서 재귀 함수 실행 

 - 방문한 노드 중 하나라도 safe node가 아니라면, 해당 노드도 safe[node] = false 처리

 

 

 

시간 복잡도: O(n), 공간 복잡도: O(n)

https://github.com/jeongum/algorithm/blob/master/LT_802_FindEventualSafeStates.kt