[구현 / Kotlin] BOJ 13459 - 구슬 탈출

문제

풀이 언어

Kotlin

코드

import java.util.*

data class Point(
    val x: Int,
    val y: Int
)

data class Points(
    val red_x: Int,
    val red_y: Int,
    val blue_x: Int,
    val blue_y: Int,
    val depth: Int
)

data class Infos(
    val x: Int,
    val y: Int,
    val cnt: Int
)

lateinit var array: Array<Array<String>>
val dx = arrayOf(1, -1, 0, 0)
val dy = arrayOf(0, 0, 1, -1)
var n = 0
var m = 0
var red = Point(0, 0)
var blue = Point(0, 0)

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    m = nextInt()

    array = Array(n) { Array(m) { "" } }

    for (i in 0 until n) {
        val input = next().chunked(1)
        for (j in 0 until m) {
            array[i][j] = input[j]
        }
    }

    // 우선 R, B의 좌표를 찾음
    find()

    // 탐색
    bfs()
}

fun find() {
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (array[i][j] == "#" || array[i][j] == ".") continue
            else if (array[i][j] == "R") red = Point(i, j)
            else if (array[i][j] == "B") blue = Point(i, j)
        }
    }
}

fun bfs() {
    var visited = Array(n) { Array(m) { Array(n) { Array(m) { 0 } } } }
    var map = LinkedList<Points>()

    map.add(Points(red.x, red.y, blue.x, blue.y, 1))
    visited[red.x][red.y][blue.x][blue.y] = 1

    while (map.isNotEmpty()) {
        val current = map.poll()

        if (current.depth > 10) break

        for (i in 0..3) {
            var redInfos = move(current.red_x, current.red_y, dx[i], dy[i])
            var blueInfos = move(current.blue_x, current.blue_y, dx[i], dy[i])

            if (array[blueInfos.x][blueInfos.y] == "O") continue
            if (array[redInfos.x][redInfos.y] == "O") {
                println(1)
                return
            }

            if (redInfos.x == blueInfos.x && redInfos.y == blueInfos.y) {
                if (redInfos.cnt > blueInfos.cnt) {
                    redInfos = Infos(redInfos.x - dx[i], redInfos.y - dy[i], redInfos.cnt)
                } else {
                    blueInfos = Infos(blueInfos.x - dx[i], blueInfos.y - dy[i], blueInfos.cnt)
                }
            }

            val points = Points(redInfos.x, redInfos.y, blueInfos.x, blueInfos.y, current.depth + 1)

            if (visited[points.red_x][points.red_y][points.blue_x][points.blue_y] == 1) continue
            visited[points.red_x][points.red_y][points.blue_x][points.blue_y] = 1

            map.add(points)
        }

    }
    println(0)
}

fun move(x: Int, y: Int, dx: Int, dy: Int): Infos {
    var nx = x
    var ny = y
    var cnt = 0

    while (array[nx + dx][ny + dy] != "#" && array[nx][ny] != "O") {
        nx += dx
        ny += dy
        cnt += 1
    }

    return Infos(nx, ny, cnt)
}

풀이 방법

BFS(혹은 DFS) 를 활용한 구현 문제이다. 구슬이 들어있는 직사각형 보드를 이리저리 굴려서 빨간 구슬을 파란 구슬보다 먼저 탈출시키면 된다. 구현 문제니까 규칙을 찾아보자.

 

1. 우선 직사각형 보드는 가장자리가 벽으로 둘러쌓여있다. 따라서 BFS 탐색 과정에서 범위를 벗어날 일이 없다.

2. 하지만 일반적인 BFS 문제와 다르게 직사각형 보드를 한쪽으로 기울이면 벽이나 구멍을 만날 떄까지 직진한다.

3. 혹은 해당 구슬보다 앞선 구슬이 있는 경우 해당 구슬과 함께 이동하게 된다.

ex) (<-이동방향-) 빨간 구슬, 파란 구슬 항상 이 형태를 유지한다.

 

이 정도의 규칙을 가지고 있고 이제 구현하면 된다.

 

1. 좌표에 대한 정보를 효율적으로 저장하기 위해 data class 를 정의했다. Pair 나 Triple 을 사용해도 된다.

data class Point(
    val x: Int,
    val y: Int
)

data class Points(
    val red_x: Int,
    val red_y: Int,
    val blue_x: Int,
    val blue_y: Int,
    val depth: Int
)

data class Infos(
    val x: Int,
    val y: Int,
    val cnt: Int
)

 

2. 입력 값은 배열에 저장한다. 띄어쓰기 가 되어 있지 않은 입력 값을 split 해야하므로 chunked 를 사용해서 분리한다.

    array = Array(n) { Array(m) { "" } }

    for (i in 0 until n) {
        val input = next().chunked(1)
        for (j in 0 until m) {
            array[i][j] = input[j]
        }
    }

 

3. 빨간 구슬 과 파란 구슬 의 좌표를 탐색한다. 초기에 정의한 Point data class 를 활용한다.

fun find() {
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (array[i][j] == "#" || array[i][j] == ".") continue
            else if (array[i][j] == "R") red = Point(i, j)
            else if (array[i][j] == "B") blue = Point(i, j)
        }
    }
}

 

4. 해당 좌표를 가지고 BFS 를 진행하면서 빨간 구슬의 탈출 여부를 판단하면 된다. 그 전에 기존 BFS 문제와는 다르게 한 칸씩 이동하는 것이 아닌 벽을 만나거나 구멍, 혹은 다른 구슬을 만날 때까지 직진하는 특성이 있으므로 이와 관련된 move 함수를 별도로 정의했다. cnt 를 카운트하는 이유는 빨간 구슬과 파란 구슬이 같은 지점에 존재할 수 있는데 이 때 처리를 해주기 위해서 이를 카운트한다.

fun move(x: Int, y: Int, dx: Int, dy: Int): Infos {
    var nx = x
    var ny = y
    var cnt = 0

    while (array[nx + dx][ny + dy] != "#" && array[nx][ny] != "O") {
        nx += dx
        ny += dy
        cnt += 1
    }

    return Infos(nx, ny, cnt)
}

 

5. 이제 진짜로 탐색을 진행하면 된다. 코드가 좀 길다.

fun bfs() {
    var visited = Array(n) { Array(m) { Array(n) { Array(m) { 0 } } } }
    var map = LinkedList<Points>()

    map.add(Points(red.x, red.y, blue.x, blue.y, 1))
    visited[red.x][red.y][blue.x][blue.y] = 1

    while (map.isNotEmpty()) {
        // linkedList로 queue 구현
        val current = map.poll()

        // 10회 이내에 탈출하지 못하면 실패
        if (current.depth > 10) break

        // 상, 하, 좌, 우 탐색 진행
        for (i in 0..3) {
            // 벽, 탈출구를 만날 때까지 직진
            var redInfos = move(current.red_x, current.red_y, dx[i], dy[i])
            var blueInfos = move(current.blue_x, current.blue_y, dx[i], dy[i])

            // 파란 구슬이 탈출하면 실패
            if (array[blueInfos.x][blueInfos.y] == "O") continue

            // 빨간 구슬이 탈출하면 성공
            if (array[redInfos.x][redInfos.y] == "O") {
                println(1)
                return
            }

            // 빨간 구슬과 파란 구슬이 같은 위치에 존재하면
            if (redInfos.x == blueInfos.x && redInfos.y == blueInfos.y) {
                // 이동 거리를 비교하여 더 멀리 이동한 구슬을 한 칸 뒤로 이동한다.
                if (redInfos.cnt > blueInfos.cnt) {
                    redInfos = Infos(redInfos.x - dx[i], redInfos.y - dy[i], redInfos.cnt)
                } else {
                    blueInfos = Infos(blueInfos.x - dx[i], blueInfos.y - dy[i], blueInfos.cnt)
                }
            }

            // 이동한 좌표와 depth++를 저장
            val points = Points(redInfos.x, redInfos.y, blueInfos.x, blueInfos.y, current.depth + 1)

            // 이미 방문한 좌표이면 continue
            if (visited[points.red_x][points.red_y][points.blue_x][points.blue_y] == 1) continue

            // 해당 좌표 방문 처리
            visited[points.red_x][points.red_y][points.blue_x][points.blue_y] = 1

            // 새로운 좌표를 queue에 삽입
            map.add(points)
        }

    }
    println(0)
}

결과

10회 이내 에 탈출하지 못한 경우 이는 실패로 간주하는데 이에 대한 조건식을 잘못 작성해서 계속 실패했다. 초기에는 상, 하, 좌, 우 에 대한 탐색을 완료한 경우에 depth++ 를 진행했는데 이는 잘못된 방법이었다. 이를 depth까지 Points 객체에 저장하는 방식으로 해결했다.