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

문제

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

13460번: 구슬 탈출 2

해설

빨간 구슬과 파란 구슬 두개가 있다.

이 중 10번 이하로 움직여서 빨간 구슬만이 구멍에 들어가게 해야한다.

만약 두 구슬 모두 구명에 빠지는 경우 -1을 출력하게 된다.

 

처음에는 빨간 구슬을 관리할 큐, 파란 구슬을 관리할 큐 이렇게 두개를 만들어 문제를 해결하려 했다.

하지만 한개의 큐로 모든 정보를 다 담고 하는 것이 더 나을 것 같아 구슬의 정보를 담을 데이터 클래스를 선언하여 큐의 자료형으로 선언하였다.

데이터 클래스와 이를 자료형으로 갖는 큐는 다음과 같다.

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

val ballPos: Queue<BallInfo> = LinkedList()

우선 입력을 받을 때, 빨간 공의 위치와 파란 공의 위치를 저장하여 큐에 넣어준다. 데이터 클래스의 cnt는 움직인 횟수를 의미하는데, 초기에는 움직이지 않은 상태이므로 0으로 시작해준다.

 

이제 구슬을 움직이며 bfs를 수행할 것이다.

for문을 통해 상하좌우 4방향으로 이동이 가능하다. #(벽)에 닿을 때까지 빨간 구슬과 파란 구슬을 이동시킨다.

벽에 닿을 때까지 움직이므로 빨간 구슬과 파란 구슬이 같은 위치에 있을 경우가 생긴다.

이는 더 많이 움직인 구슬이 더 뒤에서 움직인 것이므로 1칸 뒤로 가게 해주면 된다.

즉 같은 위치로 가더라도 위의 상황에선 파란공이 더 뒤에 있으므로 공을 모두 옮긴 후 파란 공을 한칸 뒤로 옮기면 된다.

x축 뿐만 아니라 y축으로도 이동가능한 상황이지만, 결국 둘 중 한 방향으로만 움직이므로 다음과 같이 해주면 된다.

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]
    }
}

또한 주의해야할 점으로는 파란 구슬만 구멍에 빠졌을 때는, 또 다른 경우의 수를 찾아야 되기 때문에 continue를 통해 다른 경우의 수로 넘어가야 한다.

코드

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

data class BallInfo(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<BallInfo> = LinkedList()
    ballPos.add(BallInfo(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 curCnt
        if(curCnt > 10) return -1

        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(BallInfo(nextRedBallY, nextRedBallX, nextBlueBallY, nextBlueBallX, curCnt + 1))
            }
        }
    }

    return -1
}