백준 - 구슬 탈출 2(Kotlin)

제한사항

• N, M (3 ≤ N, M ≤ 10)

문제 정리

구슬을 사방향 직선으로 움직일 수 있을 때, 빨간 구슬만 나오는 최소 움직임은?

접근 방법

일단, 최단 거리로 풀어야 하므로 BFS가 필요하다.

BFS 사용하면 맵을 최신화 하는 방법은 불가능하다.

따라서, 맵을 최신화하지 않고 구슬을 움직여야 한다.

이 때, 문제점이 발생한다. 맵을 최신화하지 않는다면 구슬의 이동을 계산할 수 없어진다.

따라서, 이동하는 방향을 정항 때, 한 구슬은 뒤로 이동하면 된다.

이동하는 방향에 빨간 구슬이 있으면, 두 구슬을 이동한 후에 파란 구슬은 뒤로 한 칸 이동한다.

반대로 이동하는 방향에 파란 구슬이 있으면, 두 구슬을 이동한 후에 빨간 구슬은 뒤로 한 칸 이동한다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList

val directions = listOf(-1 to 0, 0 to 1, 1 to 0, 0 to -1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    val map = Array(n) { readLine().toCharArray() }
    val redBallLocation = getCharLocation('R', map)
    val blueBallLocation = getCharLocation('B', map)
    val minLeanCount = bfs(redBallLocation, blueBallLocation, map)

    println(minLeanCount)
}

fun getCharLocation(character: Char, map: Array<CharArray>): Pair<Int, Int> {
    for (r in map.indices) {
        for (c in map[0].indices) {
            if (map[r][c] == character) {
                return r to c
            }
        }
    }
    return -1 to -1
}

fun bfs(redBallLocation: Pair<Int, Int>, blueBallLocation: Pair<Int, Int>, map: Array<CharArray>): Int {
    val queue = LinkedList<Pair<Int, Int>>()
    queue.add(redBallLocation)
    queue.add(blueBallLocation)
    val visited = Array(map.size) { Array(map[0].size) { Array(map.size) { BooleanArray(map[0].size) { false } } } }

    var count = 0

    while (queue.isNotEmpty()) {
        if (count >= 10) {
            return -1
        }

        val queueSize = queue.size
        for (i in 0 until (queueSize / 2)) {
            val currentRedBallLocation = queue.poll()
            val currentBlueBallLocation = queue.poll()
            if (visited[currentRedBallLocation.first][currentRedBallLocation.second][currentBlueBallLocation.first][currentBlueBallLocation.second]) {
                continue
            }
            visited[currentRedBallLocation.first][currentRedBallLocation.second][currentBlueBallLocation.first][currentBlueBallLocation.second] = true

            for (direction in directions) {
                var nextRedBallLocation: Pair<Int, Int>
                var nextBlueBallLocation: Pair<Int, Int>

                if (isRedBallFirst(currentRedBallLocation, currentBlueBallLocation, map, direction)) {
                    nextBlueBallLocation = moveDirection(currentBlueBallLocation, direction, map)
                    nextRedBallLocation = moveDirection(currentRedBallLocation, direction, map)
                    
                    if (nextRedBallLocation == nextBlueBallLocation) {
                        if (map[nextBlueBallLocation.first][nextBlueBallLocation.second] == 'O') {
                            continue
                        }
                        nextBlueBallLocation = nextBlueBallLocation.first - direction.first to nextBlueBallLocation.second - direction.second
                    }
                } else {
                    nextBlueBallLocation = moveDirection(currentBlueBallLocation, direction, map)
                    nextRedBallLocation = moveDirection(currentRedBallLocation, direction, map)

                    if (nextRedBallLocation == nextBlueBallLocation) {
                        if (map[nextBlueBallLocation.first][nextBlueBallLocation.second] == 'O') {
                            continue
                        }
                        nextRedBallLocation = nextRedBallLocation.first - direction.first to nextRedBallLocation.second - direction.second
                    }
                }

                if (visited[nextRedBallLocation.first][nextRedBallLocation.second][nextBlueBallLocation.first][nextBlueBallLocation.second]) {
                    continue
                }

                if (map[nextBlueBallLocation.first][nextBlueBallLocation.second] == 'O' || currentRedBallLocation == nextRedBallLocation && currentBlueBallLocation == nextBlueBallLocation) {
                    continue
                } else if (map[nextRedBallLocation.first][nextRedBallLocation.second] == 'O') {
                    return count + 1
                }

                queue.offer(nextRedBallLocation)
                queue.offer(nextBlueBallLocation)
            }
        }
        count++
    }

    return -1
}

fun isRedBallFirst(redBallLocation: Pair<Int, Int>, blueBallLocation: Pair<Int, Int>, map: Array<CharArray>, direction: Pair<Int, Int>): Boolean {
    var nextBlueLocation = blueBallLocation.first to blueBallLocation.second
    for (i in 0 until map.size.coerceAtLeast(map[0].size)) {
        nextBlueLocation = nextBlueLocation.first + direction.first to nextBlueLocation.second + direction.second
        if (nextBlueLocation == redBallLocation) {
            return true
        }
    }

    return false
}

fun moveDirection(ballPosition: Pair<Int, Int>, direction: Pair<Int, Int>, map: Array<CharArray>): Pair<Int, Int> {
    var currentBallPosition = ballPosition

    val count = map.size.coerceAtLeast(map[0].size)
    for (i in 1..count) {
        currentBallPosition = currentBallPosition.first + direction.first to currentBallPosition.second + direction.second

        if (map[currentBallPosition.first][currentBallPosition.second] == '#') {
            return currentBallPosition.first - direction.first to currentBallPosition.second - direction.second
        } else if (map[currentBallPosition.first][currentBallPosition.second] == 'O') {
            return currentBallPosition
        }
    }

    return currentBallPosition
}

반성

과거에 비해 확실히 고난이도 문제 풀이 실력이 늘었다. 그런데 구현이 너무 느리다. 그리고 변수명 currentLocation 이런 식으로 뒀다가 redBallLocation이랑 헷갈려서 거기서 시간을 많이 뺏겼다.

변수명을 최대한 의미 있게 두려고 노력하자.