728x90
문제
해설
흔하게 볼 수 있는 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
'PS(Problem Solving) > BOJ' 카테고리의 다른 글
[백준/BOJ] 2252번: 줄 세우기 (0) | 2022.08.15 |
---|---|
[백준/BOJ] 16234번: 인구 이동 (3) | 2022.08.14 |
[백준/BOJ] 16202번: MST 게임 (0) | 2022.08.12 |
[백준/BOJ] 2146번: 다리 만들기 (0) | 2022.08.11 |
[백준/BOJ] 11779번: 최소비용 구하기 2 (0) | 2022.08.10 |
댓글