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

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

24482번: 알고리즘 수업 - 깊이 우선 탐색 4

 

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

 

 

설명

 

트리의 경우, 탐색의 방문 순서에 관계없이 동일한 깊이를 가지겠지만,

 

문제에서 주어지는 그래프는 사이클이 있을 수 있는 그래프이기 때문에,

깊이 우선 탐색으로 탐색할 경우 탐색 순서(번호가 작은 노드부터 / 번호가 큰 노드부터)에 따라

각 노드의 깊이가 달라질 수 있습니다.

 

 

 

소스코드

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.sortDescending() }

    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)
        }
    }
}

 

각 노드를 정렬할 때, sortDescending(내림차순)으로 정렬한 것을 제외하면

3번과 동일한 코드입니다,