백준 14923 미로 탈출 Kotlin (bfs)

문제 출처 : https://www.acmicpc.net/problem/14923

14923번: 미로 탈출

문제

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다.

홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다.

이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자.

인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.

입력

N M
Hx Hy
Ex Ey
N X M 행렬

• 2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000
• 1 ≤ Hx, Hy, Ex, Ey ≤ 1000
• (Hx, Hy)≠ (Ex, Ey)
• 행렬은 0과 1로만 이루어져 있고, 0이 빈 칸, 1이 벽이다.

출력

D (탈출 할 수 없다면, -1을 출력한다.)

힌트

제일 왼쪽 위 위치에서 제일 오른쪽 아래 위치로 이동하려면 (3,2) 벽을 파괴하고 이동하면 된다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

조건이 추가된 bfs 문제이다.

벽 부수고 이동하기 문제와 비슷한데,

미로를 만나면 미로를 부수고 지나갈 한 번의 기회가 있다.

따라서 Node에는 r,c,isBroken,cnt을 프로퍼티를 갖고 이 Node를 Queue에 삽입해가며 bfs돌리면 된다.

visited[2][n][m]은 벽을 부순 경우, 부수지 않은 경우마다 방문했는지 여부를 저장한다.

 

- 다음 좌표가 그래프를 벗어난다면 스킵

- 다음 좌표가 이미 방문한 적 있다면 스킵(아래 코드에선 일단 큐에 추가하고 cur.r, cur.c로 확인하였다)

- 벽을 이미 부쉈을 때 벽을 만난다면 스킵

- 도착 좌표에 도착하면 cnt를 리턴

 

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

data class Node(
    val r: Int,
    val c: Int,
    val isBroken: Int = 0,
    val cnt: Int = 0,
)

val dir = arrayOf(
    arrayOf(0, 1),
    arrayOf(1, 0),
    arrayOf(0, -1),
    arrayOf(-1, 0)
)

fun bfs(n: Int, m: Int, sr: Int, sc: Int, er: Int, ec: Int, graph: Array<List<Int>>) : Int {
    val visited = Array(2){ Array(n) { BooleanArray(m) } }
    val q: Queue<Node> = LinkedList()
    q.add(Node(sr - 1, sc - 1))
    visited[0][sr - 1][sc - 1] = true
    while (q.isNotEmpty()) {
        val cur = q.poll()
        for (i in 0 until 4) {
            val nr = cur.r + dir[i][0]
            val nc = cur.c + dir[i][1]
            if(nr !in 0 until n || nc !in 0 until m) continue
            if (visited[cur.isBroken][nr][nc]) continue
            if (nr == er - 1 && nc == ec - 1) return cur.cnt + 1
            if (graph[nr][nc] == 1) {
                if (cur.isBroken == 1) continue
                q.add(Node(nr, nc, 1, cur.cnt + 1))
                visited[1][nr][nc] = true
            } else {
                q.add(Node(nr, nc, cur.isBroken, cur.cnt + 1))
                visited[cur.isBroken][nr][nc] = true
            }
        }
    }
    return -1
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n, m) = getIntList()
    val (sr, sc) = getIntList()
    val (er, ec) = getIntList()
    val graph = Array(n){ getIntList() }
    //solve
    write("${bfs(n, m, sr, sc, er, ec,graph)}")

    close()
}