백준 - 24444 알고리즘 수업 - 너비 우선 탐색 1
문제
24444 알고리즘 수업 - 너비 우선 탐색 1
답
kotlin code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
fun main() {
val input = readInputs()
val visitOrders = bfs(input)
printVisitOrders(visitOrders)
}
fun printVisitOrders(visitOrders: IntArray) {
visitOrders.forEach { println(it) }
}
fun bfs(input: BfsInput): IntArray {
var currentOrder = 0
val visitOrders = IntArray(input.pointCount) { currentOrder }
val queue = java.util.LinkedList<Int>()
visitOrders[input.startPoint] = ++currentOrder
queue.add(input.startPoint)
while (queue.isNotEmpty()) {
val point = queue.remove()
for(nearPoint in input.lines[point]) {
if(visitOrders[nearPoint] != 0) continue
visitOrders[nearPoint] = ++currentOrder
queue.add(nearPoint)
}
}
return visitOrders
}
fun readInputs(): BfsInput {
val firstLine = readln().split(" ").map { it.toInt() }
val input = BfsInput(firstLine[0], firstLine[1], firstLine[2] - 1)
repeat(firstLine[1]) {
val line = readln().split(" ").map { it.toInt() - 1 }
input.addLine(line[0], line[1])
}
input.sortLines()
return input
}
data class BfsInput(val pointCount: Int = 0, val lineCount: Int = 0, val startPoint: Int = 0) {
var lines = arrayOf <MutableList<Int>> ()
init {
lines = Array(pointCount) { mutableListOf() }
}
fun addLine(startPoint: Int, endPoint: Int) {
lines[startPoint].add(endPoint)
lines[endPoint].add(startPoint)
}
fun sortLines() {
lines.forEach { it.sort() }
}
}
This post is licensed under CC BY 4.0 by the author.