[백준/BOJ] 16197번: 두 동전

문제

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

16197번: 두 동전

해설

두 동전 중 하나만 보드에서 떨어트리기까지 최소 몇번을 움직여야 하는지 구해야하는 문제이다.

bfs를 이용하여 문제를 해결할 수 있다.

bfs를 수행할 때 방문여부를 체크하는데, 이 문제에서는 동전이 2개이며 각각의 (y, x)좌표를 갖고 있으므로 4차원 배열을 이용하여 방문여부배열을 선언해야 한다. 즉, 다음과 같이 선언된다.

visited[row][col][row][col]

입력을 모두 받았다면, bfs를 수행시킨다.

bfs를 수행할 큐에는 총 5개의 정보가 들어가게 된다.

que(Coin(첫번째 코인의 y좌표, 첫번째 코인의 x좌표, 두번째 코인의 y좌표, 두번째 코인의 x좌표, 움직인 횟수))

두개의 동전은 같은 방향으로 동시에 움직이므로 두 동전을 한번에 움직여준다.

동전이 움직일 수 있는 곳이라면, 그 위치를 다시 큐에 집어넣어 bfs를 계속해서 수행하고,

둘 중 하나가 떨어졌다면 현재 움직인 횟수 + 1을 반환한다. 

만약 움직인 횟수가 10을 넘어서거나, 한 개의 동전만 떨어트릴 수 있는 방법이 없다면 -1을 반환하여 출력한다.

코드

import java.util.*

data class Coin(val firstCoinY: Int, val firstCoinX: Int, val secondCoinY: Int, val secondCoinX: Int, val cnt: Int)

private lateinit var board: Array<CharArray>
private lateinit var visited: Array<Array<Array<BooleanArray>>>
private val coin = Array(2) { Pair(0, 0) }
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private var row = 0
private var col = 0

fun main() = with(System.`in`.bufferedReader()) {
    val st = StringTokenizer(readLine())
    row = st.nextToken().toInt()
    col = st.nextToken().toInt()

    board = Array(row) { CharArray(col) }
    visited = Array(row) { Array(col) { Array(row) { BooleanArray(col) } } }

    var count = 0
    repeat(row) { i ->
        val stat = readLine().toCharArray()
        repeat(col) { j ->
            board[i][j] = stat[j]
            if(board[i][j] == 'o') {
                coin[count] = Pair(i, j)
                count++
            }
        }
    }

    val ans = play()

    println(ans)
}

private fun play(): Int {
    val que: Queue<Coin> = LinkedList()
    que.add(Coin(coin[0].first, coin[0].second, coin[1].first, coin[1].second, 0))

    while(que.isNotEmpty()) {
        val coins = que.poll()
        val firstCoinY = coins.firstCoinY
        val firstCoinX = coins.firstCoinX
        val secondCoinY = coins.secondCoinY
        val secondCoinX = coins.secondCoinX
        val curCnt = coins.cnt

        if(curCnt >= 10) break

        for(i in 0 until 4) {
            var nextFirstCoinY = firstCoinY + dy[i]
            var nextFirstCoinX = firstCoinX + dx[i]
            var nextSecondCoinY = secondCoinY + dy[i]
            var nextSecondCoinX = secondCoinX + dx[i]

            if(!canMove(nextFirstCoinY, nextFirstCoinX)) {
                nextFirstCoinY = firstCoinY
                nextFirstCoinX = firstCoinX
            }

            if(!canMove(nextSecondCoinY, nextSecondCoinX)) {
                nextSecondCoinY = secondCoinY
                nextSecondCoinX = secondCoinX
            }

            var flag = 0
            if(nextFirstCoinY in 0 until row && nextFirstCoinX in 0 until col) flag++
            if(nextSecondCoinY in 0 until row && nextSecondCoinX in 0 until col) flag++

            if(flag == 1) return coins.cnt + 1
            else if(flag == 2 && !visited[nextFirstCoinY][nextFirstCoinX][nextSecondCoinY][nextSecondCoinX]) {
                visited[nextFirstCoinY][nextFirstCoinX][nextSecondCoinY][nextSecondCoinX] = true
                que.add(Coin(nextFirstCoinY, nextFirstCoinX, nextSecondCoinY, nextSecondCoinX, curCnt + 1))
            }
        }
    }

    return -1
}

private fun canMove(y: Int, x: Int): Boolean = !(y in 0 until row && x in 0 until col && board[y][x] == '#')