[백준 24481번] [Kotlin] 알고리즘 수업 - 깊이 우선 탐색 3

https://www.acmicpc.net/problem/24481

24481번: 알고리즘 수업 - 깊이 우선 탐색 3

 

난이도 : 실버 2
태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색

 

 

설명

깊이우선탐색 1, 2번이 몇 번째로 방문했는지를 출력하는 것이라면,

깊이우선탐색 3, 4번은 깊이(depth)를 출력하는 문제입니다.

 

트리의 경우, 탐색 순서가 어떻든간에 각 노드의 깊이는 모두 동일하겠지만,

해당 문제는 사이클이 존재할 수 있는 그래프에서의 DFS 탐색이기 때문에 탐색 순서에 따라 깊이가 달라질 수 있습니다.

 

 

 

 

전반적인 코드 자체는 1, 2번과 크게 다르지 않습니다.

다만 방문된 노드의 깊이를 기록해가며,

특정 노드의 a의 깊이가 3이라고 하면,

a와 연결된 b, c, d의 깊이는 a + 1을 한 4 입니다.

 

 

 

소스코드

import java.lang.StringBuilder
import java.util.*
import kotlin.collections.ArrayList

lateinit var connect: Array<ArrayList<Int>>
lateinit var visited: Array<Int>
var n = 0

fun main() = with(System.`in`.bufferedReader()) {
    val st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    val (m, start) = Array(2) { st.nextToken().toInt() }

    connect = Array(n + 1) { ArrayList<Int>() }
    visited = Array(n + 1) { -1 }

    repeat(m) {
        val st = StringTokenizer(readLine())
        val (v1, v2) = Array(2) { st.nextToken().toInt() }
        connect[v1].add(v2)
        connect[v2].add(v1)
    }
    connect.forEach { it.sort() }

    visited[start] = 0
    dfs(start)
    val sb = StringBuilder()
    for (i in 1..n) sb.append(visited[i]).append("\n")
    print(sb)
}

fun dfs(node: Int) {
    connect[node].forEach { next ->
        if (visited[next] == -1) {
            visited[next] = visited[node] + 1
            dfs(next)
        }
    }
}

 

 

 

dfs 탐색을 하면서 인접한 노드의 깊이를 현재 노드 +1 해주는 것 외에는 1, 2번과 크게 다르지 않습니다.