[백준][Kotlin] - 거울 설치(2151)

🥇️ 문제 레벨 : 골드3
🔔 문제 유형 : 다익스트라
💬 풀이 언어 : Kotlin
🖇️ 문제 링크 : 백준 문제 링크

📝 문제

채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.

 

채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.

 

채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.

 

거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.

 

거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.

🤔 문제 분석

문제에 대한 오해

이 문제를 처음 보고, '거울을 45도 기울여 설치한다.'는 문구 때문에, 빛 자체가 대각선 방향으로 이동하는 줄 알고, 아래와 같은 형태가 정답인 줄 알았다.

***#*
*...*
*!..*
*.!.*
*#***

하지만 문제를 풀이하다가, '거울이 기울어져야 하는데 어떻게 저런 정답이 나오지'라는 생각을 하게 되었다. 때문에 예제를 가지고 머릿속으로 시뮬레이션을 해보니까 내가 생각한 루트가 정답이 아니라는 것을 알게 되었다.

 

즉, 빛 자체는 상하좌우만 흐르는 것이고, 거울의 설치 각도만 45도인 것이기 때문에, 문제에서 주어진 예제의 정답 형태는 다음과 같은 것이다.

***#*
*...*
*!.!*
*...*
*#***

풀이를 하고, 또 다른 테스트 케이스를 찾으려고 보니까 나처럼 생각한 사람이 꽤나 많은 것 같았다. 나만 당한게 아닌 것 같아서 한 편으로는 뭔가 안도감이 들었다.

알고리즘 선정

이 문제는 어떤 알고리즘을 사용해야할까? 우선, 문에서 문으로 가는 최단 경로를 찾아야하기 때문에 BFS인 것 같다. 하지만, 이 문제는 거울을 최소한으로 사용해서 최단 경로를 찾는 것이다. 따라서, 설치한 거울의 개수라는 가중치가 존재하기 때문에, 다익스트라를 사용해야 한다.

BFS는 '한 번 더 이동하면 무조건 비용이 증가한다'의 느낌이고, 다익스트라는 '멀리 가도 싸게 갈 수 있고, 가까워도 비쌀 수 있다'의 느낌이다.

한 마디로, 다익스트라는 누적 가중치(비용)가 가장 작은 경로부터 우선 탐색하며, 어떤 노드에 대해 이미 더 작은 비용으로 도달한 최단 기록이 있다면 그보다 큰 비용으로 도달한 경로는 이후에 확장해도 최단경로가 될 수 없기 때문에 탐색 대상에서 제외시키는 알고리즘인 것이다.

 

이에 대한 더 자세한 내용은 아래 내용들을 보면 이해가 될 것이다.

방향 설정

이 문제는 어느 문을 출발지로 잡든 결과가 동일하다. 나는 배열을 돌면서 가장 처음 발견하는 문을 시작하는 문으로 정했다. 우선, 예제를 통해서 문제의 주인공인 채영이가 문을 열었을 때의 시야 경로를 시각화해보자.

***#*      ***#*      ***#*      ***#*      ***#*  
*.!1*      *.!1*      *.!1*      *.!1*      *.!1*  
*!.!*  =>  *!.2*  =>  *!32*  =>  *432*  =>  *432*  
*.!.*      *.!.*      *.!.*      *.!.*      *5!.*  
*#***      *#***      *#***      *#***      *#***

이 예시를 보면 알 수 있듯이, 현재 좌표(x, y), 거울 사용 개수 그리고 방향이 필요하다. 때문에, 다음과 같은 클래스 구조를 가질 필요가 있다.

private data class Sight(  
    val y: Int,  
    val x: Int,  
    val dir: Int,  
    val totalMirrorCount: Int  
)

그렇다면 다음 방향은 어떻게 설정할 수 있을까? 탐색 중 거울을 설치할 수 있는 곳에 위치하게 될 경우, 갈 수 있는 방향은 3개이다.

• 현재 바라보고 있는 방향 그대로 직진
• 거울을 현재 바라보고 있는 방향의 왼쪽으로 45도 기울여 설치
• 거울을 현재 바라보고 있는 방향의 오른쪽으로 45도 기울여 설치

방향을 틀지 않고 직진, 바라보고 있는 곳을 기준으로 왼쪽 혹은 오른쪽으로 틀기

이는 단순히 Info 클래스 안에 nextDir 함수로 넣어두면 편하게 사용할 수 있다.

// 0: 아래, 1: 왼쪽, 2: 위, 3: 오른쪽
private val dy = intArrayOf(1, 0, -1, 0)
private val dx = intArrayOf(0, -1, 0, 1)

private data class Info(
    ...
    val dir: Int
) {
    fun nextDir() = when(dir) {
        0 -> 1 to 3  
        1 -> 2 to 0  
        2 -> 3 to 1  
        3 -> 0 to 2  
        else -> throw IllegalArgumentException()
    }
}

이 함수를 통해 나온 값들은 dy, dx에 대한 인덱스 정보이다. 예를 들어, 좌측 방향(1)을 바라보고 있을 때, 갈 수 있는 방향은 2번 방향(위)과 0번 방향(아래)이 되는 것이다.

최소한의 거울 사용

이 문제는 시작하는 문에서 다음 문까지의 시야를 확보할 때, 최소한의 거울을 사용하여 도달을 해야한다. 이를 간단한 예시를 통해 확인해보자.

**!#*
*!!.*
*!.!*
*.!.*
*#***

위 예제에 있는 map[0][3]에 있는 문에서 시작해보자. 이 문에서 바라볼 수 있는 방향은 왼쪽과 아래쪽이다. 우선 왼쪽으로 시작할 경우에 시야가 다음 문까지 도달할 수 있는 루트를 시각화해보자.

**1#*  =>  **1#*  =>  **1#*  =>  **1#*    
*!!.*  =>  *!2.*  =>  *32.*  =>  *32.*    
*!.!*  =>  *!.!*  =>  *!.!*  =>  *4.!*    
*.!.*  =>  *.!.*  =>  *.!.*  =>  *5!.*    
*#***  =>  *#***  =>  *#***  =>  *#***

그리고 아래쪽 방향을 바라본 경우에 대한 루트도 시각화해보자.

**!#*  =>  **!#*  =>  **!#*  =>  **!#*  
*!!1*  =>  *!!1*  =>  *!!1*  =>  *!!1*  
*!.!*  =>  *!.2*  =>  *432*  =>  *432*  
*.!.*  =>  *.!.*  =>  *.!.*  =>  *5!.*  
*#***  =>  *#***  =>  *#***  =>  *#***

이 두 예시를 가지고, 중간 지점인 map[2][1]을 기준으로 확인해보자.

• 왼쪽 방향 시작 : 3개 설치(map[0][2], map[1][2], map[1][1])
• 아래쪽 방향 시작 : 2개 설치(map[2][3], map[2][1])

이 결과를 보면, 특정 거울에 위치할 때, 현재까지 몇 개의 거울을 사용했는지는 방향에 따라 달라지게 된다는 것을 알 수 있다. 즉, 이 정보를 알 수 있다면 더 많은 거울을 설치해서 특정 위치에 도달한 노드는 탐색하지 않고 제거(스킵)할 수 있게 되는 것이다.

 

따라서 각 위치마다 어떤 방향을 바라 봤을 때, 총 몇 개의 거울을 사용했는지에 대한 정보를 저장하기 위한 배열을 선언해주어야 한다.

val dists = Array(n) { Array(n) { IntArray(4) { Int.MAX_VALUE } } }

😎 최종 코드

메모리 : 24848 KB
시간 : 172 ms

import java.util.PriorityQueue  

private const val WALL = '*'  
private const val EMPTY = '.'  
private const val DOOR = '#'  
private const val MIRROR = '!'  

private data class Sight(  
    val y: Int,  
    val x: Int,  
    val dir: Int,  
    val totalMirrorCount: Int  
) {  
    fun nextDir() = when(dir) {  
        0 -> 1 to 3  
        1 -> 2 to 0  
        2 -> 3 to 1  
        3 -> 0 to 2  
        else -> -1 to -1  
    }  
}  

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

    val doors = ArrayList<Pair<Int, Int>>(2)  

    val map = Array(n) { i ->  
        val line = readLine()  
        CharArray(n) { j ->  
            if (line[j] == DOOR) {  
                doors.add(i to j)  
            }  
            line[j]  
        }  
    }  
    println(dijkstra(map, doors, n))  

    close()  
}  

private fun dijkstra(  
    map: Array<CharArray>,  
    doors: ArrayList<Pair<Int, Int>>,  
    n: Int  
): Int {  
    val dy = intArrayOf(1, 0, -1, 0)  
    val dx = intArrayOf(0, -1, 0, 1)  

    val pq = PriorityQueue<Sight>(compareBy { it.totalMirrorCount })  
    val dists = Array(n) { Array(n) { IntArray(4) { Int.MAX_VALUE } } }  

    val (entryY, entryX) = doors[0]  
    val (exitY, exitX) = doors[1]  

    for (dir in 0 until 4) {  
        dists[entryY][entryX][dir] = 0  
        pq.add(Sight(entryY, entryX, dir, 0))  
    }  

    while (pq.isNotEmpty()) {  
        val info = pq.poll()  
        val (y, x, dir, totalMirrorCount) = info  

        if (totalMirrorCount > dists[y][x][dir]) {  
            continue  
        }  

        val ny = y + dy[dir]  
        val nx = x + dx[dir]  

        if (ny in 0 until n && nx in 0 until n && map[ny][nx] != WALL) {  
            // 1. 거울을 설치하지 않고 직진하는 경우  
            if (dists[ny][nx][dir] > totalMirrorCount) {  
                dists[ny][nx][dir] = totalMirrorCount  
                pq.add(Sight(ny, nx, dir, totalMirrorCount))  
            }  

            // 2. 거울을 설치하고 방향을 바꾸는 경우  
            if (map[ny][nx] == MIRROR) {  
                val (opt1, opt2) = info.nextDir()  
                val nextMirrorCount = totalMirrorCount + 1  

                // 방향 전환 1
                if (dists[ny][nx][opt1] > nextMirrorCount) {  
                    dists[ny][nx][opt1] = nextMirrorCount  
                    pq.add(Sight(ny, nx, opt1, nextMirrorCount))  
                }  
                // 방향 전환 2
                if (dists[ny][nx][opt2] > nextMirrorCount) {  
                    dists[ny][nx][opt2] = nextMirrorCount  
                    pq.add(Sight(ny, nx, opt2, nextMirrorCount))  
                }  
            }  
        }  
    }  

    return dists[exitY][exitX].minOrNull() ?: -1  
}