PS(Problem Solving)/BOJ

[백준/BOJ] 2665번: 미로만들기

JunsuKim 2022. 8. 13.
728x90

문제

 

2665번: 미로만들기

첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

www.acmicpc.net

해설

흔하게 볼 수 있는 BFS 문제이다.

미로를 탐색하며 도착점에 도달하기 위해 바꿔야하는 검은 방이 몇개인지 알아야 한다.

서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어 지나다닐 수 있으므로, 상하좌우로 이동이 가능하다.

보통 BFS라면 방문 여부를 체크하는 배열이 있기 마련이다. 이를 통해 이미 방문했던 지점이라면 재방문을 하지 않도록 해준다.

하지만  난 이 문제에서 재방문을 허용해주었다.

모든 경우 재방문을 하는 것이 아닌, 벽을 바꾼 횟수가 더 적을 수 있을 때, 재방문을 통해 더 적은 횟수로 갱신을 해주는 것이다.

이를 반복하며 미로의 끝에 도착했을 때, 계속해서 변경횟수가 더 적은 것으로 갱신되며 진행됬으므로, 가장 적게 변경시킨 횟수가 저장되게 된다.

코드

import java.util.*

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

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    miro = Array(n) { IntArray(n) }
    change = Array(n) { IntArray(n) { Int.MAX_VALUE } }

    repeat(n) { i ->
        val stat = readLine()
        repeat(n) { j ->
            miro[i][j] = stat[j] - '0'
        }
    }

    move(n)
    println(change[n-1][n-1])
}

private fun move(n: Int) {
    val que: Queue<Pair<Int, Int>> = LinkedList()
    que.add(Pair(0, 0))
    change[0][0] = 0

    while(que.isNotEmpty()) {
        val cur = que.poll()
        val curY = cur.first
        val curX = cur.second

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

            if(!checkCondition(n, nextY, nextX)) continue

            if(miro[nextY][nextX] == 1) {
                if(change[nextY][nextX] > change[curY][curX]) {
                    change[nextY][nextX] = change[curY][curX]
                    que.add(Pair(nextY, nextX))
                }
            }
            else {
                if(change[nextY][nextX] > change[curY][curX] + 1) {
                    change[nextY][nextX] = change[curY][curX] + 1
                    que.add(Pair(nextY, nextX))
                }
            }
        }
    }
}

private fun checkCondition(n: Int, y: Int, x: Int): Boolean = (y in 0 until n && x in 0 until n)
728x90

댓글