[백준/BOJ] 1261번: 알고스팟

문제

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

해설

상하좌우로 움직이며 목표지까지 최소 몇개의 벽을 부수어야 하는지 구하는 문제이다.

bfs를 이용해서 문제를 풀었는데, 보통 bfs라면 Queue를 이용하지만 이 문제에서는 우선순위 큐(Priority Queue)를 사용하였다.

우선순위 큐를 사용한 이유는 최단거리로 가는 문제가 아닌, 최소의 벽을 부수는 문제이기 때문이다.

우선순위의 기준을 벽을 부순 개수로 오름차순하면, 목표 지점에 도착했을 때, 최소로 벽을 부순 개수를 구할 수 있다.

소스 코드

import java.util.*

private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private lateinit var map: Array<IntArray>

data class Point(val y: Int, val x: Int, val cnt: Int): Comparable<Point> {
    override fun compareTo(other: Point): Int = cnt - other.cnt
}

fun main() = with(System.`in`.bufferedReader()) {
    val (col, row) = readLine().split(" ").map { it.toInt() }

    map = Array(row) { IntArray(col) }
    repeat(row) { i ->
        val state = readLine().toCharArray()
        repeat(col) { j ->
            map[i][j] = state[j] - '0'
        }
    }

    println(bfs(row, col))
}

private fun bfs(row: Int, col: Int): Int {
    val visited = Array(row) { BooleanArray(col) }
    visited[0][0] = true

    val pq = PriorityQueue<Point>()
    pq.add(Point(0, 0, 0))

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        val curY = cur.y
        val curX = cur.x
        val curCnt = cur.cnt

        if(curY == row - 1 && curX == col - 1) return curCnt

        for(i in 0 until 4) {
            val nextY = curY + dy[i]
            val nextX = curX + dx[i]

            if(nextY !in 0 until row || nextX !in 0 until col) continue

            if(!visited[nextY][nextX]) {
                visited[nextY][nextX] = true
                if(map[nextY][nextX] == 0) pq.add(Point(nextY, nextX, curCnt))
                else pq.add(Point(nextY, nextX, curCnt + 1))
            }
        }
    }

    return 0
}