리코쳇 로봇 - kotlin

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

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

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

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

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

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

풀이 과정

한 방향으로 이동하기 시작하면 장애물이나 끝에 닿을때까지 이동해야 하는 좌표 이동문제다. 시작지점과 끝지점을 찾아주고 일반적으로 이동하는 방법을 while을 통해 이동할 수 없을때까지 이동해주면 된다고 이해했다.

// 다음 이동 지점을 찾는 함수
fun findRoad(
    x: Int,
    y: Int,
    board: Array<String>,
    dx: Int,
    dy: Int
): Pair<Int, Int> {
    var currentX = x
    var currentY = y
    while (true) {
        if (currentX + dx == -1 || currentX + dx == board.size)
            return Pair(currentX, currentY)
        if (currentY + dy == -1 || currentY + dy == board[0].length)
            return Pair(currentX, currentY)
        if (board[currentX + dx][currentY + dy] == 'D')
            return Pair(currentX, currentY)
        currentX += dx
        currentY += dy
    }
}


fun solution(board: Array<String>): Int {
    var answer = Int.MAX_VALUE
    val dx = intArrayOf(0, 1, 0, -1)
    val dy = intArrayOf(-1, 0, 1, 0)
    val queueList = mutableListOf<Triple<Int, Int, Int>>()
    val visited = MutableList(board.size) { MutableList(board[0].length) { Int.MAX_VALUE } }

    // 시작 지점 찾기
    board.forEachIndexed { i, sList ->
        if (sList.contains('R')) {
            queueList.add(Triple(i, sList.indexOf('R'), 0))
        }
    }
    
	// 큐가 빌때까지 BFS
    while (queueList.isNotEmpty()) {
        val temp = queueList.removeLast()
        val current = Pair(temp.first, temp.second)
        val count = temp.third

        if (board[current.first][current.second] == 'G') {
            answer = Math.min(answer, count)
        }

        for (i in 0..3) {
            val toGoNode = findRoad(current.first, current.second, board, dx[i], dy[i])
            if (toGoNode != current && visited[toGoNode.first][toGoNode.second] > count + 1) {
                queueList.add(Triple(toGoNode.first, toGoNode.second, count + 1))
                visited[toGoNode.first][toGoNode.second] = count + 1
            }
        }
    }

    return if (answer == Int.MAX_VALUE) -1 else answer
}

처음에는 Map에 Boolean으로 방문했는지만 기록했으나, 다음 방문에 더 적은 횟수로 도달할 수 있는 경우가 있었고 Map을 Int형으로 변환해 이동 횟수가 적은 경우만 계산하고 기록하는 방법으로 해결할 수 있었다.