Home 백준 - 24444 알고리즘 수업 - 너비 우선 탐색 1
Post
Cancel

백준 - 24444 알고리즘 수업 - 너비 우선 탐색 1

문제

24444 알고리즘 수업 - 너비 우선 탐색 1

screencaptures

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.

백준 - 2447 별 찍기 - 10

백준 - 24445 알고리즘 수업 - 너비 우선 탐색 2