[Kotlin] 99 클럽 코딩 테스트 스터디 미들러 33일차 - 리코쳇 로봇 (BFS)

https://school.programmers.co.kr/learn/courses/30/lessons/169199?language=kotlin

프로그래머스

[문제]

리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

다음은 보드게임판을 나타낸 예시입니다.

 

... D.. R

. D.G...

.... D.D

D.... D.

.. D....

 

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

 

[입출력 예]

 

[풀이]

'최단 경로'를 찾는 문제는 BFS를 활용하여 처리하겠습니다. 주의할 점은 해당 문제에서 로봇은 그냥 빈 공간만 움직여서 되는 것이 아니라 벽이나 장애물(D)을 통해 멈추기 때문에 G에 도달하더라도 완료된 것이 아니라 멈출 때까지 가야 합니다.

즉 방문 불가능한 지역에 도달해야겠습니다.

바로 이전에 풀었던 DFS 활용 무인도 탐색 문제와 비슷한 부분이 있습니다. 일단 좌표 기반 처리이기 때문에 Visited 배열과 이동 방향이 들어갈 Directions가 각각 2차원, Pair로 선언되었습니다.

fun solution(board: Array<String>): Int {
    val n = board.size
    val m = board[0].length
    val directions = arrayOf(Pair(0, 1), Pair(1, 0), Pair(0, -1), Pair(-1, 0))
    val visited = Array(n) { BooleanArray(m) { false } }
    
    ....

 

그리고 이번엔 시작 위치가 0, 0이 아니라 출발점의 좌표 R를 찾아놓고 시작해야 합니다.

var startX = 0
var startY = 0

for (i in 0 until n) {
    for (j in 0 until m) {
        if (board[i][j] == 'R') {
            startX = i
            startY = j
            break
        }
    }
}

visited[startX][startY] = true

 

그리고 BFS는 현재 노드에서 인접한 모든 노드를 먼저 탐색 후, 다음 레벨로 이동하는 방식입니다. 이때, 큐를 활용하여 순서를 유지할 수 있습니다. 경로별 X, Y 좌표와 이동 거리 값을 축적하기 위해 Position이라는 데이터 클래스를 활용했습니다.
(Queue 생성 시, Tripple을 활용할 수는 없었습니다.)

val queue: Queue<Position> = LinkedList()
queue.offer(Position(startX, startY, 0))

초기 위치 값에 대해 offer 해줍니다.

 

이제 큐에서 위치를 하나씩 꺼내어 상, 하, 좌, 우로 이동이 가능한 조건인지 체크해주어야 합니다.

tripple 변수로 데이터를 큐에서 꺼내주고, 목표 지점에 도달한 경우인지 체크해 줍니다.

while (queue.isNotEmpty()) {
        val (x, y, moves) = queue.poll()
        
        // 목표 지점(G)에 도달한 경우
        if (board[x][y] == 'G') return moves
        
        ....

 

Pair 기반으로 선언했던 상하좌우 Directions 배열을 반복문 돌면서 한 방향에 대해 멈출 때까지 x, y 값을 계산해 줍니다.

멈추지 않는다면 잊지 말고 반드시 다음 X, Y 값으로 업데이트해주어야 합니다!

 for (dir in directions) {
    var nx = x
    var ny = y

    // 한 방향으로 계속 이동
    while (true) {
        val nextX = nx + dir.first
        val nextY = ny + dir.second

        // 가능한 인덱스 범위가 아니거나 장애물 마주치면 중지
        if (nextX !in 0 until n || nextY !in 0 until m || board[nextX][nextY] == 'D') break

        // 계속 다음 방향으로 업데이트
        nx = nextX
        ny = nextY
    }

 

이제 Position에 들어간 cnt 값을 업데이트해주어야 합니다.

새로운 도달 위치가 방문하지 않은 곳일 때 방문 처리 및 cnt 값을 업데이트해 주면 되겠습니다.

if (!visited[nx][ny]) {
    visited[nx][ny] = true
    queue.offer(Position(nx, ny, moves + 1))
}

 

전체 코틀린 코드입니다.

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

fun solution(board: Array<String>): Int {
    val n = board.size
    val m = board[0].length
    val directions = arrayOf(Pair(0, 1), Pair(1, 0), Pair(0, -1), Pair(-1, 0))
    val visited = Array(n) { BooleanArray(m) { false } }

    var startX = 0
    var startY = 0

    for (i in 0 until n) {
        for (j in 0 until m) {
            if (board[i][j] == 'R') {
                startX = i
                startY = j
                break
            }
        }
    }
    visited[startX][startY] = true

    val queue: Queue<Position> = LinkedList()
    queue.offer(Position(startX, startY, 0))

    while (queue.isNotEmpty()) {
        val (x, y, moves) = queue.poll()!!

        if (board[x][y] == 'G') return moves

        for (dir in directions) {
            var nx = x
            var ny = y

            while (true) {
                val nextX = nx + dir.first
                val nextY = ny + dir.second
                if (nextX !in 0 until n || nextY !in 0 until m || board[nextX][nextY] == 'D') break

                nx = nextX
                ny = nextY
            }

            if (!visited[nx][ny]) {
                visited[nx][ny] = true
                queue.offer(Position(nx, ny, moves + 1))
            }
        }
    }
    return -1
}

BFS DFS는 상당히 어렵네요.. 머리가 아프지만 계속 가야 합니다.