백준 6087 레이저 통신 Kotlin (다익스트라)

문제 출처 : https://www.acmicpc.net/problem/6087

6087번: 레이저 통신

문제

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

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

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

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

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

입력

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

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

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

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

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 다익스트라

풀이

Bfs 혹은 다익스트라 문제이다.

bfs 응용이 다익스트라이긴 한데 무튼 그렇다.

우선순위 큐는 사용해도 되고 안 해도 된다. 우선순위 큐를 사용한다면 목적지에 처음 도착한 값이 바로 정답이 될 것이고, 그냥 큐를 사용한다면 여러 번 방문했을 때 최솟값을 저장해 놓아야 한다.

따라서 bfs 돌릴 때 분기 처리만 잘 하면 정수를 저장하는 2차원 visited 배열 + bfs로 끝난다.

풀이는 다음과 같다.

 

1. 두 개의 C 좌표를 저장한다.

2. 하나의 C에서 bfs를 시작한다.

3. 큐에서 가져갈 값은 r,c 좌표, 방향, 거울 설치 횟수이다.

4. 큐에 초기값으로 하나의 C좌표에서 4방향으로 시작한다.

5.1 탐색 조건은 일반적인 bfs 의 조건에서 방향에 따른 분기가 추가된다.

5.2 방향을 상, 우, 하, 좌 이런 순서로 dir 배열을 만들어 놓는다면, (현재 방향 +2)%4 값이 다음 방향과 같을 때 탐색을 진행하지 않는다.

(이 경우 완전 반대 방향으로 꺾는 것으로, 문제에서 불가능한 탐색이다.)

5.3 현재 방향과 다음 방향이 같지 않다면 나머지 경우는 모두 90도 꺾이는 경우(거울이 설치된 경우)이다.

5.4 목적지에 도착한 경우 visited[][]값만 갱신하고, 큐에 추가하진 않는다.

6. 목적지에 저장된 거울 설치 횟수의 최솟값을 출력한다.

 

 

코드

import java.util.*
val br = System.`in`.bufferedReader()

fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
fun chToInt(ch: Char) = Character.getNumericValue(ch)

lateinit var graph: Array<String>
lateinit var visited: Array<IntArray>
var start =  ArrayList<Pair<Int,Int>>(2)
val dir = arrayOf(
    arrayOf(-1,0),//상
    arrayOf(0,1),//우
    arrayOf(1,0),//하
    arrayOf(0,-1)//좌
)
data class Node(
    val r: Int,
    val c: Int,
    val d: Int,
    val cnt: Int
)

fun bfs(n: Int, m: Int): Int{

    val q: Queue<Node> = LinkedList()

    for(d in 0 until 4) {
        q.add(Node(start[0].first, start[0].second, d, 0))
    }

    while(q.isNotEmpty()){
        val (r,c,d,cnt) = q.poll()
        if(cnt> visited[r][c]) continue
        for(i in 0 until 4){
            val nr = r+dir[i][0]
            val nc = c+dir[i][1]
            var nCnt = cnt
            if(nr !in 0 until n || nc !in 0 until m) continue
            if(graph[nr][nc] == '*') continue
            if((i+2)%4==d) continue
            //방향 전환
            if(i!=d) nCnt++
            if(nCnt>visited[nr][nc]) continue
            visited[nr][nc] = nCnt
            if(graph[nr][nc] == 'C'){
                continue
            }
            q.add(Node(nr,nc,i,nCnt))
        }
    }
    return visited[start[1].first][start[1].second]
}

fun main() = with(System.out.bufferedWriter()){

    //input
    val (m,n) = getIntList()
    visited = Array(n){IntArray(m){Int.MAX_VALUE} }
    graph = Array(n){r ->
        br.readLine().apply{
            this.forEachIndexed { index, c ->
                if (c == 'C') {
                    start.add(Pair(r, index))
                }
            }
        }
    }

    //solve, output
    write("${bfs(n,m)}")

    close()
}