[백준] 레이저 통신 - 골드 3 (Kotlin)

문제

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸
  'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

풀이

• 완전 탐색
• C를 찾아서 C 위치에서 탐색 시작
• 나머지 C 를 찾을 때 까지 완전 탐색을 한다.
• 탐색 시, 진행 방향과 현재까지 방향 전환을 한 횟수를 전달한다.
• 진행 방향이 바뀐다면 방향 전환 횟수를 1 증가
• C 에 도달했을 때 방향 전환 횟수를 비교해 최솟값을 저장

소스코드

import java.util.*

fun main() {
    val solution = Solution()

    solution.solution()
}
/*
7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......
 */
/**
 * 완전 탐색
 * C를 찾아서 C 위치에서 탐색 시작
 * 나머지 C 를 찾을 때 까지 완전 탐색을 한다.
 * 탐색 시, 진행 방향과 현재까지 방향 전환을 한 횟수를 전달한다.
 * 진행 방향이 바뀐다면 방향 전환 횟수를 1 증가
 * C 에 도달했을 때 방향 전환 횟수를 비교해 최솟값을 저장
 */
const val INF = 123456789
class Solution {
    var dx = intArrayOf(0, 1, 0, -1)
    var dy = intArrayOf(1, 0, -1, 0)
    var result = 123456789
    fun solution() {
        val input = readLine()!!.split(' ')
        val W = input[0].toInt()
        val H = input[1].toInt()
        val graph = Array(H) { Array(W) { '.' } }
        var visit = Array(H) { Array(W) { false } }
        val queue = PriorityQueue<Node>()
        var start = Pair(0, 0)
        repeat(H) {
            graph[it] = readLine()!!.toCharArray().toTypedArray()
        }

        loop@ for (y in 0 until H) {
            for (x in 0 until W) {
                if (graph[y][x] == 'C') {
                    start = Pair(x, y)
                    break@loop
                }
            }
        }

        queue.offer(Node(start.first, start.second, -1, -1))

        while (queue.isNotEmpty()) {
            val now = queue.poll()

            if (now.x !in 0 until W || now.y !in 0 until H) continue
            if (graph[now.y][now.x] == '*') continue
            if (visit[now.y][now.x]) continue
            if (graph[now.y][now.x] == 'C' && now.count != -1) {
                result = result.coerceAtMost(now.count)
                continue
            }

            visit[now.y][now.x] = true

            for (dir in 0 until 4) {
                val nx = now.x + dx[dir]
                val ny = now.y + dy[dir]

                val count = if (now.dir != dir) now.count + 1 else now.count

                queue.offer(Node(nx, ny, count, dir))
            }
        }

        dx = intArrayOf(1, 0, -1, 0)
        dy = intArrayOf(0, -1, 0, 1)
        visit = Array(H) { Array(W) { false } }

        queue.offer(Node(start.first, start.second, -1, -1))

        while (queue.isNotEmpty()) {
            val now = queue.poll()

            if (now.x !in 0 until W || now.y !in 0 until H) continue
            if (graph[now.y][now.x] == '*') continue
            if (visit[now.y][now.x]) continue
            if (graph[now.y][now.x] == 'C' && now.count != -1) {
                result = result.coerceAtMost(now.count)
                continue
            }

            visit[now.y][now.x] = true

            for (dir in 0 until 4) {
                val nx = now.x + dx[dir]
                val ny = now.y + dy[dir]

                val count = if (now.dir != dir) now.count + 1 else now.count

                queue.offer(Node(nx, ny, count, dir))
            }
        }

        dx = intArrayOf(0, -1, 0, 1)
        dy = intArrayOf(1, 0, 1, 0)
        visit = Array(H) { Array(W) { false } }

        queue.offer(Node(start.first, start.second, -1, -1))

        while (queue.isNotEmpty()) {
            val now = queue.poll()

            if (now.x !in 0 until W || now.y !in 0 until H) continue
            if (graph[now.y][now.x] == '*') continue
            if (visit[now.y][now.x]) continue
            if (graph[now.y][now.x] == 'C' && now.count != -1) {
                result = result.coerceAtMost(now.count)
                continue
            }

            visit[now.y][now.x] = true

            for (dir in 0 until 4) {
                val nx = now.x + dx[dir]
                val ny = now.y + dy[dir]

                val count = if (now.dir != dir) now.count + 1 else now.count

                queue.offer(Node(nx, ny, count, dir))
            }
        }

        dx = intArrayOf(-1, 0, 1, 0)
        dy = intArrayOf(0, 1, 0, -1)
        visit = Array(H) { Array(W) { false } }

        queue.offer(Node(start.first, start.second, -1, -1))

        while (queue.isNotEmpty()) {
            val now = queue.poll()

            if (now.x !in 0 until W || now.y !in 0 until H) continue
            if (graph[now.y][now.x] == '*') continue
            if (visit[now.y][now.x]) continue
            if (graph[now.y][now.x] == 'C' && now.count != -1) {
                result = result.coerceAtMost(now.count)
                continue
            }

            visit[now.y][now.x] = true

            for (dir in 0 until 4) {
                val nx = now.x + dx[dir]
                val ny = now.y + dy[dir]

                val count = if (now.dir != dir) now.count + 1 else now.count

                queue.offer(Node(nx, ny, count, dir))
            }
        }

        println(result)
    }
}

data class Node(
    val x: Int,
    val y: Int,
    val count: Int,
    val dir: Int
) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return when {
            count > other.count -> 1
            count < other.count -> -1
            count == other.count -> 0
            else -> INF
        }
    }
}

/*
println("[${now.y}, ${now.x}] : ${now.count} ${when(now.dir) {
                0 -> "아래"
                1 -> "오른쪽"
                2 -> "위"
                3 -> "왼쪽"
                else -> ""
            }
            }")
 */

요약 및 정리

일단, 처음엔 같은 알고리즘을 생각했긴 했지만 DFS로 풀이했다. 하지만 DFS로는 C-C까지 탐색을 하긴하되 최단 거리. 즉, 최소 갯수인 거울의 수를 구하지 못햇다. 그래서 BFS와 다익스트라 알고리즘을 합쳐서 우선 순위 큐에 비굣값을 거울의 갯수(방향 전환 횟수)로 잡고 풀이를 했고, 그게 아래의 코드였다.

...
queue.offer(Node(start.first, start.second, -1, -1))

        while (queue.isNotEmpty()) {
            val now = queue.poll()

            if (now.x !in 0 until W || now.y !in 0 until H) continue
            if (graph[now.y][now.x] == '*') continue
            if (visit[now.y][now.x]) continue
            if (graph[now.y][now.x] == 'C' && now.count != -1) {
                result = result.coerceAtMost(now.count)
                continue
            }

            visit[now.y][now.x] = true

            for (dir in 0 until 4) {
                val nx = now.x + dx[dir]
                val ny = now.y + dy[dir]

                val count = if (now.dir != dir) now.count + 1 else now.count

                queue.offer(Node(nx, ny, count, dir))
            }
        }
        ...
data class Node(
    val x: Int,
    val y: Int,
    val count: Int,
    val dir: Int
) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return when {
            count > other.count -> 1
            count < other.count -> -1
            count == other.count -> 0
            else -> INF
        }
    }
}

이 방법으로 정답을 시도했는데, 문제는 BFS 성질에 따라 넓이 우선으로 탐색하기 때문에 같은 위치를 방문했을 때 발생한다. 즉, visit = true 로 체크된 곳을 방문했을 때 거울의 갯수가 더 적음에도 이미 방문했기에 체크하지 못하는 점이었다. 아래의 그림을 보면

두 번째의 경우, (1, 0) 에서 아래로 쭉 내려가면 거울의 갯수가 1이되고, 첫 번째의 경우, (0, 2), (1, 2) 에서 거울의 갯수가 2개가 되어 정답은 1이 되어야한다.
하지만 탐색 순서가 아래 -> 오른쪽 이라고 할 때, 문제가 발생한다.
(0, 1) -> (1, 0) -> (0, 2) -> (1, 2) -> (1, 1)가 되어버리고
(1, 0) -> (1, 1) -> (1, 2) 의 경로로 내려올 때 거울의 갯수가 1임에도 불구하고 (0, 2) -> (1, 2) 오른쪽으로 오는 경로로 먼저 들어오기 때문에 거울의 갯수가 2개가 필요한 경로를 선택해버리게 된다.
(억지라고 생각할 수도 있는데 실제로 그랬다. 천천히 순서를 복기해보면 알 수 있다.)
따라서, 나의 경우는 무식하게 탐색 순서를 4번을 모두 돌려서 풀이했고, 다시 생각해보니 visit 배열을 boolean -> int 로 변경하여 방문했을 때의 거울의 갯수를 저장하고, 방문했던 곳을 다시 방문했을 때는 현재의 거울의 갯수가 더 작다면 갱신해주는 방법을 사용하면 풀 수 있다.