[백준 16954번] 움직이는 미로 탈출

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

16954번: 움직이는 미로 탈출

 

난이도 : 골드 3
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

1. 설명

BFS를 사용한 4방향 델타 탐색 문제입니다

일반 문제와 다른 부분은, 미로가 1초마다 내려온다는 점이죠.

때문에 한 회차마다 이동을 하며 이동이 모두 끝난 뒤 모든 칸을 1만큼 내리는 과정을 반복합니다.

 

 

1.1. 상하좌우 + 대각선 8방향 탐색 + 제자리

      

      

      

    
    

      <kotlin />
    
val dx = intArrayOf(-1, -1, -1, 0, 0, 1, 1, 1, 0)
val dy = intArrayOf(-1, 0, 1, -1, 1, -1, 0, 1, 0)

 

상하좌우와 대가선 8방향에 대해 dx, dy를 지정하고,

제자리에 가만히 있기 역시 가능하기 때문에 마지막에 (0,0)도 추가해줬습니다.

 

 

 

1.2. 한 회차마다 BFS를 돌리기

한 회차마다 이동을 하는 방법은 큐에 저장된 원소의 개수만큼 BFS를 돌리는 것인데요.

      

      

      

    
    

      <kotlin />
    
while (q.isNotEmpty()) {
    val visited = Array(n) { BooleanArray(n) }

    for (i in 0..<q.size) {
        val target = q.poll()

        // BFS 진행
        for(i in dx.size) {
            (생략)
            q.add(Node(nx, ny))
        }
    }
    
    (벽 내리기)
}

 

큐의 size 씩 BFS를 수행하고,

또 다시 큐에 원소를 넣음으로써 한 회차마다 BFS를 진행할 수 있습니다.

 

 

 

1.3. 벽 내리기

      

      

      

    
    

      <kotlin />
    
fun wallDown(map: Array<CharArray>) {
    for (i in map.size - 1 downTo 1) {
        for (j in map[i].indices) {
            map[i][j] = map[i - 1][j]
        }
    }
    map[0] = CharArray(map[0].size) { '.' }
}

 

벽 내리기의 경우, 그냥 for문을 사용하여 바로 윗 칸의 원소를 가져왔습니다.

가장 윗 칸의 경우 '.'으로 지정해줬습니다.

 

 

 

2. 소스코드

      

      

      

    
    

      <kotlin />
    
import java.util.*

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

fun main() = with(System.`in`.bufferedReader()) {
    val n = 8
    val map = Array(n) { readLine().toCharArray() }
    val dx = intArrayOf(-1, -1, -1, 0, 0, 1, 1, 1, 0)
    val dy = intArrayOf(-1, 0, 1, -1, 1, -1, 0, 1, 0)

    val q = LinkedList<Node>() as Queue<Node>
    q.add(Node(7, 0))

    while (q.isNotEmpty()) {
        val visited = Array(n) { BooleanArray(n) }

        for (i in 0..<q.size) {
            val target = q.poll()
            if (map[target.x][target.y] == '#') continue
            if (target.x == 0 && target.y == 7) {
                println(1)
                return
            }

            for (j in 0..<9) {
                val nx = target.x + dx[j]
                val ny = target.y + dy[j]
                if (nx !in 0..<n || ny !in 0..<n || map[nx][ny] == '#' || visited[nx][ny]) continue
                visited[nx][ny] = true
                q.add(Node(nx, ny))
            }
        }

        wallDown(map)
    }

    println(0)
}

fun wallDown(map: Array<CharArray>) {
    for (i in map.size - 1 downTo 1) {
        for (j in map[i].indices) {
            map[i][j] = map[i - 1][j]
        }
    }
    map[0] = CharArray(map[0].size) { '.' }
}