[ 백준 16197 ] - 두 동전 (Kotlin)

 

16197번: 두 동전

 

문제 이해

두 개의 동전 중 하나만을 떨어뜨리기 위해 눌러야하는 최소의 버튼 횟수를 구하는 문제였다.

 

bfs를 사용하면 처음으로 동전 하나만 떨어지는 경우가 최소 횟수가 되므로, bfs를 선택

 

풀이

• bfs를 사용하면 그리 어렵지 않게 풀 수 있는 문제인 것 같다.
• 큐 두 개로 동전 각각의 위치를 매번 갱신하면서 동전이 하나만 떨어지는지를 체크하면 된다
• 동전이 하나만 떨어지는 경우는 xor를 사용하면 간단히 체크할 수 있다.

if(coin1Dropped xor coin2Dropped){ // 코인 하나만 떨어진 경우
    return cnt
}

---

• 해당 문제에서 주의할 점은 아래와 같다.

1. 동전이 움직이지 못하는 경우 현재 위치를 큐에 넣어주어야 함
   
   • 동전이 움직이지 않는다고해서 큐에 넣지않고 넘어가면 안된다.
   • 두 개의 동전이 동시에 움직이기 때문에 동전 두 개의 큐를 같이 관리 해줘야한다.
2. 떨어뜨릴 수 없는 경우를 체크할 필요가 없다.
   • 최소 횟수를 구하는 것은 쉬웠으나, 떨어뜨릴 수 없는 경우의 조건을 찾는게 좀 힘들었다.
   • 문제 조건 중 버튼을 10번보다 많이 눌러야한다면, -1을 출력하라는 조건이 있다.
   • 즉, 떨어뜨릴 수 없는 경우는 체크할 필요 없이 버튼을 10번 이상 누른 순간 -1을 출력하고 끝내면 된다.

---

소스 코드

package BOJ16197

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.collections.ArrayList

data class Coin(val x:Int, val y:Int)

lateinit var map:ArrayList<String>
val dx = arrayOf(-1, 0, 1, 0)
val dy = arrayOf( 0,-1, 0, 1)

fun Queue<Coin>.addCoin(next:Coin, cur:Coin) = this.add(if(map[next.x][next.y] == '#') cur else next)
fun isDropped(n:Int, m:Int, p:Coin) = p.run { (x < 0 || y < 0 || x >= n || y >= m) }

/**
 * o : 동전
 * . : 빈 칸
 * # : 벽
 * 동전이 이동하려는 칸이 벽(#)이면, 동전은 이동하지 않는다.
 * 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
 * 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.
 */
fun bfs(n:Int, m:Int, coin:ArrayList<Coin>):Int{
    val coin1q = LinkedList<Coin>().apply { add(coin[0]) }
    val coin2q = LinkedList<Coin>().apply { add(coin[1]) }
    val cntQ = LinkedList<Int>().apply { add(1) }

    while(!coin1q.isEmpty() && !coin2q.isEmpty()){
        val coin1 = coin1q.poll()
        val coin2 = coin2q.poll()
        val cnt = cntQ.poll()

        if(cnt > 10) return -1

        for (i in 0 until 4){
            val next_coin1 = Coin(coin1.x + dx[i], coin1.y + dy[i])
            val next_coin2 = Coin(coin2.x + dx[i], coin2.y + dy[i])

            val coin1Dropped = isDropped(n,m, next_coin1) // 범위 밖이면 떨어진 것
            val coin2Dropped = isDropped(n,m, next_coin2)
            // 코인 하나만 떨어진 경우
            if(coin1Dropped xor coin2Dropped) return cnt

            // 둘 다 안 떨어진 경우
            if (!coin1Dropped && !coin2Dropped) {
                coin1q.addCoin(next_coin1, coin1)
                coin2q.addCoin(next_coin2, coin2)
                cntQ.add(cnt + 1)
            }
            // 둘 다 떨어진 경우는 더 이상 진행 불가
        }
    }

    return -1
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val coin:ArrayList<Coin> = arrayListOf()
    map = arrayListOf()

    repeat(n){
        st = StringTokenizer(readLine())
        map.add(st.nextToken())

        repeat(m) { m ->
            if (map.last()[m] == 'o') {
                coin.add(Coin(map.size-1, m))
            }
        }
    }

    println(bfs(n,m,coin))
}