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

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

24483번: 알고리즘 수업 - 깊이 우선 탐색 5

 

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

 

 

설명

깊이 우선 탐색 1번 + 3번이라고 볼 수 있습니다.

방문 순서를 체크하는 1번과 깊이를 체크하는 3번을 잘 풀었다면 쉽게 푸실 수 있을 겁니다.

 

 

개념 자체는 1-2번, 3-4번과 동일합니다.

오름차순으로 방문할 경우,

방문 순서는 1 -> 2 -> 4 -> 5 -> 3 -> 6 순으로 방문하며,

깊이는 1번 :0, 2번: 1, 3번:1, 4번: 2, 5번 : 3, 6번 : 2로,

사이클이 있을 수 있는 그래프이기 때문에 방문 순서에 따라 노드의 깊이가 달라질 수 있습니다.

 

각 노드의 방문 순서와 깊이를 곱한 결과는 다음과 같습니다.

---

	1번 노드	2번 노드	3번 노드	4번 노드	5번 노드	6번 노드
순서	1	2	5	3	4	6
깊이	0	1	1	2	3	2
순서 * 깊이	0	3	6	6	12	12

---

0 + 3 + 6 + 6 + 12 + 12 = 35로

위와 같은 방법으로 답을 구할 수 있습니다.

 

 

 

소스코드

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

lateinit var connect: Array<ArrayList<Int>>
lateinit var depth: Array<Int>
lateinit var sequence: Array<Int>
var sequenceIdx = 2
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>() }
    depth = Array(n + 1) { -1 }
    sequence = Array(n + 1) { 0 }

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

    depth[start] = 0
    sequence[start] = 1
    dfs(start)
    var sum = 0L
    for(i in 1 .. n) sum += depth[i].toLong() * sequence[i].toLong()
    println(sum)
}

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

 

 

 

후기

알고리즘 수업 - 깊이 우선 탐색 5번째 시리즈입니다.

마지막 6번째가 남았네요.