[백준][코틀린][6087] 레이저 통신

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

6087번: 레이저 통신

문제 풀이

1. 현재 위치(x, y), 현재 거울 개수, 레이저 방향을 저장하는 Laser Data Class 를 만든다.

2. 주어진 입력에서 C 지점을 laserArea 에 저장한다.

3. laserArea[0] 의 값을 시작으로 BFS 를 수행한다.

4. Queue 에는 1번에서 만든 Laser Class 를 넣고 초기 값으로는 3번에서 찾은 값을 넣는다.

이때 거울 개수를 -1 로 설정한다. 왜냐하면 처음 C 지점에서 시작할때 레이저 방향이 상하좌우로 될 수 있기 때문에 -1 로 방향을 설정하고

방향이 -1이 되면 nextMirror 값이 증가되기 때문에 거울 개수 초기 값을 -1로 해야 한다.

5. 거울 최소 개수를 저장하는 mirrorCount 3차원 Int 배열을 선언한다. (0: X 좌표, 1: Y좌표, 2: 현재 방향)

6. 레이저 방향은 0은 상, 1은 하, 2는 좌, 3은 우로 정한다.

7. BFS 탐색 시 다음의 조건이 될 경우 다음 탐색을 수행한다.

8. 탐색되는 좌표가 범위를 벗어날 경우 다음 탐색을 수행한다.

9. 탐색되는 좌표의 map 값이 * 일 경우 벽이므로 다음 탐색을 수행한다.

10. mirrorCount 값이 거울 개수보다 크면 값을 업데이트 한다.

11. 최소 값을 저장한 뒤 결과를 출력한다.

코드

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (W, H) = br.readLine().split(" ").map { it.toInt() }
    val map = Array(H) { CharArray(W) { '.'} }
    repeat(H) { index ->
        map[index] = br.readLine().toCharArray()
    }

    // 두 개의 C 를 찾아 시작 지점과 종료 지점을 저정한다.
    val laserArea = mutableListOf<Pair<Int, Int>>()

    for (i in 0 until H) {
        for (j in 0 until W) {
            if (map[i][j] == 'C') {
                laserArea.add(Pair(i, j))
            }
        }
    }

    println("${bfs(H, W, map, laserArea)}")
}

private fun bfs(H: Int, W: Int, map: Array<CharArray>, laserArea: MutableList<Pair<Int, Int>>): Int {
    var result = Int.MAX_VALUE
    val queue = LinkedList<Laser>()
    queue.add(Laser(laserArea[0].first, laserArea[0].second, -1, -1))
    // 현재위치의 각 방향에 대한 거울 수를 저장한다.
    val mirrorCount = Array(H) { Array(W) { IntArray(4) { Int.MAX_VALUE } } }

    while (queue.isNotEmpty()) {
        val current = queue.pop()
        val dX = intArrayOf(-1, 1,  0, 0)
        val dY = intArrayOf( 0, 0, -1, 1)

        if (current.x == laserArea[1].first && current.y == laserArea[1].second) {
            result = Math.min(result, current.mirrorCount)
        } else {
            //println("current $current")

            for (i in 0..3) {
                val nX = current.x + dX[i]
                val nY = current.y + dY[i]

                //범위 밖
                if ((nX < 0 || nX >= H) || (nY < 0 || nY >= W)) continue
                //벽으로 된 영역
                if (map[nX][nY] == '*') continue

                if (current.direction == 0 && i == 1) continue
                if (current.direction == 1 && i == 0) continue
                if (current.direction == 2 && i == 3) continue
                if (current.direction == 3 && i == 2) continue

                val nextMirrorCount = if (current.direction == i) current.mirrorCount else current.mirrorCount + 1
                //println("next >> ($nX, $nY), ${current.direction}, $i / $nextMirrorCount, ${mirrorCount[nX][nY][i]}")

                if (mirrorCount[nX][nY][i] > nextMirrorCount) {
                    mirrorCount[nX][nY][i] = nextMirrorCount
                    queue.add(Laser(nX, nY, nextMirrorCount, i))
                }
            }
        }
    }

    return result
}

private data class Laser(
    // 현재 빛의 위치 X 좌표
    val x: Int,
    // 현재 빛의 위치 Y 좌표
    val y: Int,
    // 현재까지 세운 거울의 수
    val mirrorCount: Int,
    // 빛이 어느 방향으로 가는 지 확인
    // 0: 상, 1: 하, 2: 좌, 3: 우
    val direction: Int
)