[Joco][백준/BOJ] 15653 번: 구슬 탈출 4

[문제]

15653번: 구슬 탈출 4

[깃허브]

GitHub - Dev-Joco/algorithm-kotlin: Algorithm(Kotlin)

 

문제 요약

• 빨간 구슬과 파란 구슬이 하나씩 들어있는 보드판을 (상, 하, 좌, 우)로 기울여가며 구슬을 구멍으로 꺼내는 게임.
• 보드를 한 번 기울이면, 구슬이 이동할 수 있는 곳까지 쭉 미끌어진다.
• 두 개의 구슬은 겹칠 수 없다.
• 구멍은 하나이며, 빨간 구슬이 구멍으로 빠져나오게 하는 최단 시간을 구하라
• (단, 같은 시각에 파란 구슬도 구멍에 빠지면 안된다)

 

제한 조건

• 시간 제한: 2초
• 메모리 제한: 512MB
• 보드판의 크기 N, M (3 ≤ N, M ≤ 10)

 

풀이

• BFS 문제
• visited[red_row][red_col][blue_row][blue_col] 사용
• 큐에는 빨/파 구슬의 위치를 동시에 저장.
• 두 구슬의 위치가 겹쳤을 때,  각 구슬의 이전 위치와 비교하여 상대적으로 멀리서 온 구슬을 뒤에 배치함

 

[Solution.kt]

import java.util.ArrayDeque
import kotlin.math.absoluteValue

private val Int.abs: Int
    get() = absoluteValue

private val MOVE = arrayOf(
    intArrayOf(0, -1), // 좌
    intArrayOf(-1, 0), // 상
    intArrayOf(0, 1), // 우
    intArrayOf(1, 0), // 하
)

fun main() {
    // (3 ≤ N, M ≤ 10)
    val (N, M) = readln().split(" ").map { it.toInt() }.toIntArray()

    val board = Array(N) { charArrayOf() }
    val startPos = IntArray(4)

    for (r in 0 until N) {
        board[r] = readln().toCharArray()
        board[r].forEachIndexed { c, ch ->
            if (ch == 'R') {
                startPos[0] = r
                startPos[1] = c
                board[r][c] = '.'
            } else if (ch == 'B') {
                startPos[2] = r
                startPos[3] = c
                board[r][c] = '.'
            }
        }
    }

    solution(N, M, board, startPos).let { println(it) }
}

private fun solution(N: Int, M: Int, board: Array<CharArray>, start: IntArray): Int {
    val queue = ArrayDeque<IntArray>()
    val visited = Array(N) { Array(M) { Array(N) { BooleanArray(M) } } }

    queue.offer(start)
    visited[start[0]][start[1]][start[2]][start[3]] = true

    var time = 0
    var isSucceed = false

    while (queue.isNotEmpty()) {
        time += 1

        for (q in queue.indices) {
            val curr = queue.poll() ?: break

            for (dir in 0..3) {
                val next = getNext(board, curr, dir)

                if (next[2] == -1) { // 파란 구슬이 구멍에 빠짐
                    continue
                } else if (next[0] == -1) { // 빨간만 구슬에 빠짐
                    isSucceed = true
                    queue.clear()
                    break
                }

                if (visited[next[0]][next[1]][next[2]][next[3]])
                    continue

                visited[next[0]][next[1]][next[2]][next[3]] = true
                queue.offer(next)
            }
        }
    }

    return if (isSucceed) time else -1
}

private fun getNext(board: Array<CharArray>, curr: IntArray, dir: Int): IntArray {
    var (r1, c1, r2, c2) = curr
    val next = intArrayOf(-1, -1, -1, -1)

    var isRedGoal = false
    var isBlueGoal = false

    while (board[r1][c1] == '.') {
        r1 += MOVE[dir][0]
        c1 += MOVE[dir][1]
    }

    if (board[r1][c1] == 'O') {
        isRedGoal = true
    } else {
        next[0] = r1 - MOVE[dir][0]
        next[1] = c1 - MOVE[dir][1]
    }

    while (board[r2][c2] == '.') {
        r2 += MOVE[dir][0]
        c2 += MOVE[dir][1]
    }

    if (board[r2][c2] == 'O') {
        isBlueGoal = true
    } else {
        next[2] = r2 - MOVE[dir][0]
        next[3] = c2 - MOVE[dir][1]
    }
    
    if (!isRedGoal && !isBlueGoal) {
        if (r1 == r2 && c1 == c2) { // 두 구슬이 겹쳤을 때
            val redDiff = (next[0] - curr[0]).abs + (next[1] - curr[1]).abs
            val bluDiff = (next[2] - curr[2]).abs + (next[3] - curr[3]).abs

            if (redDiff > bluDiff) { // 빨간 공이 멀리서 옴
                next[0] -= MOVE[dir][0]
                next[1] -= MOVE[dir][1]
            } else { // 파란 공이 멀리서 옴
                next[2] -= MOVE[dir][0]
                next[3] -= MOVE[dir][1]
            }
        }
    }

    return next
}