[백준/BOJ] 13459번: 구슬 탈출

문제

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

13459번: 구슬 탈출

해설

이전에 구슬 탈출2 문제를 풀고 구슬 탈출1문제도 있을 것 같아 검색해보니 역시나 있었다.

구슬 탈출2 이 글을 보고 오는 것을 추천한다.

 

이 문제와 구슬 탈출2 문제는 출력에만 차이가 있고, 다를 것이 없다.

구슬 탈출2 문제에서는 빨간 구슬이 탈출하는데 최소 몇 번 움직여야 하는지를 출력하는 것이고, 이 문제는 탈출할 수 있다면 1, 없다면 0을 출력하는 것이다. 즉, 반환값에만 차이가 있다는 것이다.

코드

import java.util.*
import kotlin.math.abs

data class MarbleInfo(val redY: Int, val redX: Int, val blueY: Int, val blueX: Int, val cnt: Int)

private lateinit var map: Array<CharArray>
private lateinit var visited: Array<Array<Array<BooleanArray>>>
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private var redBall = Pair(0, 0)
private var blueBall = Pair(0, 0)
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()

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

    repeat(row) { i ->
        val stat = readLine().toCharArray()
        repeat(col) { j ->
            map[i][j] = stat[j]

            if(map[i][j] == 'R') redBall = Pair(i, j)
            if(map[i][j] == 'B') blueBall = Pair(i, j)
        }
    }

    println(move())
}

private fun move(): Int {
    val ballPos: Queue<MarbleInfo> = LinkedList()
    ballPos.add(MarbleInfo(redBall.first, redBall.second, blueBall.first, blueBall.second, 0))

    visited[redBall.first][redBall.second][blueBall.first][blueBall.second] = true

    while(ballPos.isNotEmpty()) {
        val cur = ballPos.poll()
        val curRedBallY = cur.redY
        val curRedBallX = cur.redX
        val curBlueBallY = cur.blueY
        val curBlueBallX = cur.blueX
        val curCnt = cur.cnt

        visited[curRedBallY][curRedBallX][curBlueBallY][curBlueBallX] = true

        if(map[curRedBallY][curRedBallX] == 'O') return 1
        if(curCnt > 10) return 0

        for(i in 0 until 4) {
            var nextRedBallY = curRedBallY
            var nextRedBallX = curRedBallX
            var nextBlueBallY = curBlueBallY
            var nextBlueBallX = curBlueBallX

            while(true) {
                nextRedBallY += dy[i]
                nextRedBallX += dx[i]

                if(map[nextRedBallY][nextRedBallX] == '#') {
                    nextRedBallY -= dy[i]
                    nextRedBallX -= dx[i]
                    break
                }

                if(map[nextRedBallY][nextRedBallX] == 'O') break
            }

            while(true) {
                nextBlueBallY += dy[i]
                nextBlueBallX += dx[i]

                if(map[nextBlueBallY][nextBlueBallX] == '#') {
                    nextBlueBallY -= dy[i]
                    nextBlueBallX -= dx[i]
                    break
                }

                if(map[nextBlueBallY][nextBlueBallX] == 'O') break
            }

            if(map[nextBlueBallY][nextBlueBallX] == 'O') continue

            if(nextRedBallY == nextBlueBallY && nextRedBallX == nextBlueBallX) {
                val moveRedBall = abs(nextRedBallY - curRedBallY) + abs(nextRedBallX - curRedBallX)
                val moveBlueBall = abs(nextBlueBallY - curBlueBallY) + abs(nextBlueBallX - curBlueBallX)

                if(moveRedBall > moveBlueBall) {
                    nextRedBallY -= dy[i]
                    nextRedBallX -= dx[i]
                }
                else {
                    nextBlueBallY -= dy[i]
                    nextBlueBallX -= dx[i]
                }
            }

            if(!visited[nextRedBallY][nextRedBallX][nextBlueBallY][nextBlueBallX]) {
                ballPos.add(MarbleInfo(nextRedBallY, nextRedBallX, nextBlueBallY, nextBlueBallX, curCnt + 1))
            }
        }
    }

    return 0
}