백준 16197 두 동전 Kotlin (bfs)

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

16197번: 두 동전

문제

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.

버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

• 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
• 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

• o: 동전
• .: 빈 칸
• #: 벽

동전의 개수는 항상 2개이다.

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 백트래킹

풀이

간단한 bfs같지만 은근히 까다롭다.

까다롭다기보단, 일반적인 bfs지만 두 개의 동전을 동시에 컨트롤해야 한다는 점 때문에 몇 가지 분기를 추가해야 한다.

우선 그래프를 입력받고, 두 동전의 위치를 저장해놨다가, 큐를 시작할 때 초기값으로 넣는 것은 쉽게 알 수 있을 것이다.

이후 bfs를 돌리는 로직이 핵심인데 본인의 풀이는 다음과 같다.

 

1. bfs의 while문 안에 turn, val size = q.size 을 이용해 턴을 구분해 준다.

2. 매 턴마다 두 개의 동전(a,b)을 꺼내서 두 동전의 인접 4방향(다음 노드)을 검사한다.

3. a혹은 b의 다음 노드가 그래프를 나간다면 outCount를 증가시킨다.

4. a혹은 b의 다음 노드가 벽을 만난다면 다음 노드가 아닌 원래 노드의 좌표를 큐에 푸시한다.

5. 이 외의 경우는 모두 큐에 푸시한다.

6. 같은 턴에 큐에서 꺼낸 두 개의 동전 세트를 인접 4방향으로 돌리면서, outCount가 1인 경우 현재 turn을 반환한다.

 

위의 과정에서 3번 과정을 제외하곤 항상 큐에 푸시하여 탐색을 이어나가는 것을 알 수 있다.

이는 동전이 벽에 부딪혀도 탐색을 끝내는 게 아니라 현재 자리에 머무는 것을 의미하며, 이래야 이 보드게임에서 동전 하나만 밖으로 떨구는 스킬을 구사할 수 있다.

턴을 구현할 때는 노드를 두 개씩 꺼내고 두 개씩 삽입하기 때문에, size/2를 반복문의 범위로 설정해야 함에 주의하자.

 

 

코드

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

fun getIntGraph() = br.readLine().split(' ').map { it.toInt() }

val dir = arrayOf(
    arrayOf(0,1),
    arrayOf(1,0),
    arrayOf(0,-1),
    arrayOf(-1,0)
)
lateinit var graph: Array<String>
val startCoin = ArrayList<Pair<Int,Int>>()
fun bfs(n: Int, m: Int):Int{

    val q: Queue<Pair<Int,Int>> = LinkedList()
    for(coin in startCoin){
        q.add(coin)
    }
    var turn=1
    while(q.isNotEmpty()){
        val size = q.size
        for(i in 0 until size/2){
            val cur1 = q.poll()
            val cur2 = q.poll()
            for(j in 0 until 4){
                var outCount =0
                val nr1 = cur1.first + dir[j][0]
                val nc1 = cur1.second + dir[j][1]
                val nr2 = cur2.first + dir[j][0]
                val nc2 = cur2.second + dir[j][1]
                if(nr1 !in 0 until n || nc1 !in 0 until m){
                    outCount++
                }
                else if(graph[nr1][nc1]=='#'){
                    q.add(cur1)
                }
                else{
                    q.add(Pair(nr1,nc1))
                }
                if(nr2 !in 0 until n || nc2 !in 0 until m){
                    outCount++
                }
                else if(graph[nr2][nc2]=='#'){
                    q.add(cur2)
                }
                else{
                    q.add(Pair(nr2,nc2))
                }
                if(outCount==1){
                    return turn
                }
            }
        }
        turn++
        if(turn>10) return -1
    }

    return -1
}

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

    //input
    val(n,m) = getIntGraph()
    graph = Array(n){r->
        br.readLine().also {
        for(c in it.indices){
            if(it[c]=='o'){
                startCoin.add(Pair(r,c))
            }
        }
    } }

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

    close()
}