문제

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

답

kotlin code

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