[백준] 2178 (미로 탐색)

#1 알고리즘

그래프 - 너비 우선 탐색 (BFS, Breadth-First Search)

bfs 알고리즘으로 풀었다.

 

#2 코드 - 코틀린

import java.util.*

var Y = -1
var X = -1
lateinit var miro: Array<Array<Int>>

const val WALL = 0

fun main() {
    // (1) make miro and make discovered for bfs
    val yAndX = readln().split(" ")
    Y = yAndX[0].toInt()
    X = yAndX[1].toInt()
    miro = Array(Y) { Array(X) { -1 } }
    for (y: Int in 0..<Y) {
        val row = readln().toCharArray()
        for (x: Int in 0..<X) {
            miro[y][x] = row[x].toString().toInt()
        }
    }

    // (2) bfs
    bfs(0, 0)

    // (3) print
    println(miro[Y - 1][X - 1])
}

fun bfs(startY: Int, startX: Int) {
    val queue: Queue<Pair<Int, Int>> = LinkedList()
    val visited = Array(Y) { Array(X) { false } }

    queue.add(Pair(startY, startX))
    visited[startY][startX] = true
    miro[startY][startX] = 1

    while (queue.isNotEmpty()) {
        val prev = queue.poll()
        val prevY = prev.first
        val prevX = prev.second

        for (next in getNexts(prevY, prevX)) {
            val nextY = next.first
            val nextX = next.second
            if (!visited[nextY][nextX]) {
                queue.add(Pair(nextY, nextX))
                visited[nextY][nextX] = true
                miro[nextY][nextX] = miro[prevY][prevX] + 1
            }
        }
    }
}

fun getNexts(y: Int, x: Int): List<Pair<Int, Int>> {
    val candidates = listOf(
        Pair(y - 1, x),
        Pair(y + 1, x),
        Pair(y, x - 1),
        Pair(y, x + 1)
    )

    val nexts = ArrayList<Pair<Int, Int>>()
    for (candidate in candidates) {
        val candidateY = candidate.first
        val candidateX = candidate.second
        if ((candidateY in 0..<Y) && (candidateX in 0..<X) && (miro[candidateY][candidateX] != WALL)) {
            nexts.add(candidate)
        }
    }
    return nexts
}