[백준][Kotlin] 미로 탐색 - 2178번

문제 링크 : https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1 복사

4 6
101111
101010
101011
111011

예제 출력 1 복사

15

---

일반적인 N x M 매트릭스에서의 BFS 문제이다.

import java.util.*
import java.util.stream.IntStream

val Y_BOUND = arrayOf(0, 0, 1, -1)
val X_BOUND = arrayOf(1, -1, 0, 0)
const val POSITION = "position"
const val COUNT = "count"

fun main() {
    val (row, col) = readLine()?.split(' ')!!.map { it.toInt() }.take(2)
    val vertexList: MutableList<MutableList<Vertex>> = mutableListOf()

    for (i in 0 until row) {
        vertexList.add(mutableListOf())
        readLine()?.forEachIndexed { j, it ->
            vertexList[i].add(j, Vertex(position = Position(i, j), possible = it == '1'))
        }
    }

    println(bfs(row, col, vertexList))
}

data class Vertex(
    val position: Position,
    var check: Boolean = false,
    val possible: Boolean,
) {
    fun visit() {
        check(!check) { "(y, x) = (${position.y}, ${position.x})'s check is true" }
        check = true
    }

    fun getNeighborPosition(): List<Position> = IntStream.range(0, 4)
        .toArray()
        .map {
            Position(position.y + Y_BOUND[it], position.x + X_BOUND[it])
        }
}

data class Position(val y: Int, val x: Int)

private fun bfs(row: Int, col: Int, vertexList: List<List<Vertex>>): Int {
    val queue = LinkedList<Map<String, Any>>()

    vertexList[0][0].visit()
    queue.offer(mapOf(POSITION to Position(0, 0), COUNT to 1))

    while (!queue.isEmpty()) {
        val poll = queue.poll()
        val (y, x) = poll[POSITION] as Position
        val currentCount = poll[COUNT] as Int

        if (y == row - 1 && x == col - 1) {
            return currentCount
        }

        for ((nextY, nextX) in vertexList[y][x].getNeighborPosition()) {
            if (nextY < 0 ||
                nextX < 0 ||
                nextY > row - 1 ||
                nextX > col - 1 ||
                vertexList[nextY][nextX].check ||
                !vertexList[nextY][nextX].possible
            ) {
                continue
            }

            vertexList[nextY][nextX].visit()
            queue.offer(mapOf(POSITION to Position(nextY, nextX), COUNT to currentCount + 1))
        }
    }

    throw IllegalArgumentException("Wrong Logic.")
}