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

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

24484번: 알고리즘 수업 - 깊이 우선 탐색 6

 

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

 

 

설명

깊이 우선 탐색 1-2번 + 3-4번을 합친 형태면서,

깊이 우선 탐색 5번의 내림차순 방문 버전입니다.

 

 

1~5번을 푸신 분들이라면 별로 어렵지 않게 푸실 수 있을 문제입니다.

---

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

---

0 + 4 + 2 + 18 + 10 + 6 = 40으로,

5번과는 오름차순 <-> 내림차순 방문만 다를 뿐, 풀이방식은 동일합니다.

 

 

 

소스코드

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

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

 

 

 

후기

알고리즘 탐색 - 깊이 우선 탐색 시리즈의 마지막 6번 문제였습니다.

DFS는 BFS와 더불어 코딩테스트를 응시할 때 매우 자주 나오는 유형이므로,

알아두시면 매우 유용하게 쓰실 수 있습니다.