(Kotlin) 움직이는 미로 탈출 - Gold 5

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

16954번: 움직이는 미로 탈출

 

문제

욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.

 

이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

 

1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

 

욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

 

입력

8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.

 

출력

욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.

 

 

풀이

BFS로 풀 수 있는 그래프 문제인데, 특징은 벽이 아래로 움직인다는 것이다. 벽과 캐릭터가 충돌하면 캐릭터는 더이상 움직일 수 없고, 캐릭터는 인접 방향, 대각선 방향으로 움직이거나 제자리에 있을 수도 있다.

 

큐에 있는 모든 캐릭터를 BFS에 따라 모든 방향으로 한 칸씩만 움직인다. 제자리에 있는 것도 가능하다는 것이다. 난 이걸 빼먹어서 틀렸다..ㅋ. 주의할 점은 벽의 위치에 따라 상황이 달라지므로 중복 방문은 체크하면 안되는데, 같은 턴 내에서는 체크를 해도 된다.

한 칸의 BFS 순회가 끝나면 벽을 움직여서 상황에 맞게 캐릭터와 벽을 소멸시킨다. 그리고 이 과정을 반복해서 BFS 전체 프로세스가 끝나기 전에 목표에 도달하면 1을, 그러지 못하면 0을 반환한다.

 

좌표(Point)를 data class로 만들어서 캐릭터와 캐릭터의 움직임(dPoint)을 표현했으며, ArrayDeque을 사용해서 큐를 구현했다.

그리고 벽은 움직이거나 소멸시키기 위해 리스트에 따로 저장해서 관리했고, Pair를 사용해서 좌표로 표현했다.

 

 

코드

fun main(){
    data class Point(var x: Int, var y: Int)

    var wallList = mutableListOf<Pair<Int, Int>>()
    val queue = ArrayDeque<Point>()
    val dPoint = arrayListOf(Point(0, 0),
        Point(0, -1), Point(1, -1), Point(1, 0), Point(1, 1), Point(0, 1), Point(-1, 1), Point(-1, 0), Point(-1, -1)
    )

    repeat(8) { i ->
        readLine()!!.forEachIndexed { j, ch ->
            if (ch == '#') wallList.add(Pair(j, i))
        }
    }

    queue.add(Point(0, 7))

    while (queue.isNotEmpty()) {
        val queueSize = queue.size

        repeat(queueSize) { _ ->
            val character = queue.removeFirst()

            for (d in dPoint) {
                val newPoint = Point(character.x + d.x, character.y + d.y).also {
                    if (it.x == 7 && it.y == 0) {
                        println(1)
                        return
                    }
                }

                if (newPoint.x in 0..7 && newPoint.y in 0..7 && Pair(newPoint.x, newPoint.y) !in wallList) {
                    queue.add(newPoint)
                }
            }
        }

        val removingList = mutableListOf<Point>()
        wallList = wallList
            .asSequence()
            .filter{ it.second+1 < 8 }
            .map{
                for(character in queue){
                    if (it.first == character.x && it.second+1 == character.y){ removingList.add(character) }
                }
                Pair(it.first, it.second + 1)}
            .toMutableList()

        removingList.forEach { queue.remove(it) }
    }
    println(0)
}

 

리뷰

코틀린으로 백준 형식의 문제와 그래프 문제를 처음 풀어봤는데, 어색했고 파이썬으로 풀 때보다 어려웠다. 

 

코드가 객체로도 좌표를 표현하고, Pair로도 좌표를 나타내고 있어서 비효율에 중구난방이 됐다.

곰곰이 생각해보니까 좌표를 사용하는데, 그래프는 사용하지 않는 것에서부터 뒤죽박죽이 됐다. 그래서 벽이랑 캐릭터 충돌을 확인할 때마다 반복문을 돌리고 있다. 정리가 더 필요하다.