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

문제

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

15644번: 구슬 탈출 3

해설

이전 문제인 구슬 탈출 2문제랑의 차이점은 출력에 경로가 추가된 것밖에 없다.

앞부분은 구슬 탈출 2문제랑 같으므로 저 글을 확인하도록 하자.

 

이제 경로를 추가해야 한다.

데이터 클래스에 경로를 저장할 route라는 변수를 추가해주었다.

이제 움직인 방향에 따라 왼쪽이라면 "L", 오른쪽이라면 "R", 위라면 "U", 아래라면 "D"를 더해주면 된다.

코드

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, val route: String)

private lateinit var map: Array<CharArray>
private lateinit var visited: Array<Array<Array<BooleanArray>>>
private lateinit var redBall: Pair<Int, Int>
private lateinit var blueBall: Pair<Int, Int>
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private var row = 0
private var col = 0
private var ansCnt = 0
private var ansRoute = ""

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

    move()
}

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

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

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

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

        if(curCnt > 10) {
            println(-1)
            return
        }
        if(map[curRedBallY][curRedBallX] == 'O') {
            println(curCnt)
            println(curRoute)
            return
        }

        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]) {
                when(i) {
                    0 -> marbleQue.add(MarbleInfo(nextRedBallY, nextRedBallX, nextBlueBallY, nextBlueBallX, curCnt + 1, curRoute + "R"))
                    1 -> marbleQue.add(MarbleInfo(nextRedBallY, nextRedBallX, nextBlueBallY, nextBlueBallX, curCnt + 1, curRoute + "L"))
                    2 -> marbleQue.add(MarbleInfo(nextRedBallY, nextRedBallX, nextBlueBallY, nextBlueBallX, curCnt + 1, curRoute + "D"))
                    3 -> marbleQue.add(MarbleInfo(nextRedBallY, nextRedBallX, nextBlueBallY, nextBlueBallX, curCnt + 1, curRoute + "U"))
                }
            }
        }
    }
    println(-1)
}