[백준 6087번] [Kotlin] 레이저 통신

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

6087번: 레이저 통신

 

난이도 : 골드 3
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 데이크스트라, 최단 경로

 

 

설명

레이저를 쐈을 때, 방향을 좌측 혹은 우측으로 90도 회전할 수 있는 거울을 최소로 놓아

레이저를 목표 지점까지 도달시키는 문제입니다.

 

저는 BFS를 응용하여 풀이했는데요.

한 거울마다 90도씩 회전할 수 있기 때문에 현재 레이저의 방향 역시 좌표에 저장해야 합니다.

따라서 저는 n * m * 4(상하좌우 4방향) 3차원 배열을 사용하였습니다.

 

레이저는 방해물이 없다면 쭉 뻗어나갑니다.

따라서 한 번의 탐색마다 벽이나 맵의 끝을 마주칠 때 까지,

해당 방향의 좌표를 모두 방문처리 및 큐에 넣어줍니다.

 

또한, 거울을 설치하여 레이저를 90도 좌우로 회전할 수 있기에,

val dx = intArrayOf(-1, 0, 1, 0)
val dy = intArrayOf(0, -1, 0, 1)

 

dx, dy의 인덱스를 -1 or 1 해주면 좌우 회전 효과를 볼 수 있도록 설정하였습니다.

이후 4방향 탐색 대신 dx, dy를 -1 or 1 해주며 좌우 방향을 대상으로도 벽 혹은 맵의 마지막 칸 까지 탐색을 진행합니다.

 

 

 

소스코드

import java.util.*

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

val dx = intArrayOf(-1, 0, 1, 0)
val dy = intArrayOf(0, -1, 0, 1)

fun main() = with(System.`in`.bufferedReader()) {
    val (m, n) = readLine().split(" ").map { it.toInt() }

    val map = Array(n) { readLine().toCharArray() }
    val points = ArrayList<Node>()

    repeat(n) { x ->
        repeat(m) { y ->
            if (map[x][y] == 'C') points.add(Node(x, y, 0))
        }
    }

    val (start, end) = points
    val queue = LinkedList<Node>() as Queue<Node>
    val visited = Array(n) { Array(m) { IntArray(4) } }

    repeat(4) {
        queue.add(Node(start.x, start.y, it))
        visited[start.x][start.y][it] = 1
    }

    while (queue.isNotEmpty()) {
        val (x, y, dir) = queue.poll()

        for (deltaDir in arrayOf(1, -1)) {
            for (distance in 1..100) {
                var nd = dir + deltaDir
                if (nd == -1) nd = 3
                if (nd == 4) nd = 0

                val nx = x + dx[nd] * distance
                val ny = y + dy[nd] * distance

                if (nx !in 0..<n || ny !in 0..<m || map[nx][ny] == '*') break
                if (visited[nx][ny][nd] != 0) continue

                if (nx == end.x && ny == end.y) {
                    println(visited[x][y][dir] - 1)
                    return
                }

                visited[nx][ny][nd] = visited[x][y][dir] + 1
                queue.add(Node(nx, ny, nd))
            }
        }
    }
}

 

 

 

후기

 

예전에 도전했을 때 해결법이 떠오르지 않아 고민했던 문제였는데,

오랜만에 다시 보니 풀이법이 떠올라 9개월만에 맞췄습니다.

머리를 식힌 뒤 문제를 다시 보면 새로운 시각으로 접근할 수 있는 것 같아요.