[백준/BOJ] 1660번: 말이 되고픈 원숭이

문제

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

해설

출발점에서 도착점까지 움직일 때, 최소로 움직일 수 있는 값을 출력하는 문제로 BFS를 사용하여 문제를 풀 수 있었다.

원숭이는 상하좌우로 움직일 수 있고, k번 이하로 말처럼 움직일 수 있다고 한다.

나는 이를 말이 움직일 수 있는 좌표와 원숭이가 움직일 수 있는 좌표로 각각 저장해주었다.

private val monkeyX = intArrayOf(1, -1, 0, 0)
private val monkeyY = intArrayOf(0, 0, 1, -1)
private val horseX = intArrayOf(-2, -1, 1, 2, -2, -1, 1, 2)
private val horseY = intArrayOf(1, 2, 2, 1, -1, -2, -2, -1)

한번 방문한 위치는 재방문할 필요가 없으므로 visited 배열을 통해 방문 여부 처리를 해주었다.

이때 visited 배열을 2차원 배열로 하면 원숭이가 기본적으로 움직였을 때랑, 말처럼 움직였을 때를 구분 지을 수 없다.

따라서 3차원 배열로 선언하여 말처럼 움직였을 때와 기본적(상하좌우)로 움직였을 때를 구분해주었다.

즉 visited[y좌표][x좌표][말처럼 움직인 횟수]가 된다. 말처럼 움직인 횟수는 기존 입력받은 값으로 해서 말처럼 움직일 때마다 --를 통해 값을 줄여주었다.

 

말처럼 이동한 횟수가 0보다 크다면 아직 말처럼 이동이 가능하므로 총 8방향으로 움직여준다.

만약 0이라면 더 이상 말처럼 움직일 수 없으므로 상하좌우로만 움직이게 해 준다.

 

BFS가 종료됐을 때, 도착점에 도착을 하지 못했다면 Integer.MAX_VALUE를 반환해주었다.

main에서 BFS 함수의 반환값을 받았을 때 이 값이 Integer.MAX_VALUE라면 -1을 출력하고, 아니라면 그 값을 출력해주면 된다.

코드

import java.util.*

data class Monkey(val y: Int, val x: Int, val cnt : Int, val canMoveLikeHorse: Int)

private lateinit var map: Array<IntArray>
private lateinit var visited: Array<Array<BooleanArray>>
private val monkeyX = intArrayOf(1, -1, 0, 0)
private val monkeyY = intArrayOf(0, 0, 1, -1)
private val horseX = intArrayOf(-2, -1, 1, 2, -2, -1, 1, 2)
private val horseY = intArrayOf(1, 2, 2, 1, -1, -2, -2, -1)

fun main() = with(System.`in`.bufferedReader()) {
    val canMoveLikeHorse = readLine().toInt()
    val (col, row) = readLine().split(" ").map { it.toInt() }

    map = Array(row) { IntArray(col) }
    visited = Array(row) { Array(col) { BooleanArray(canMoveLikeHorse + 1) } }

    repeat(row) { i ->
        val st = StringTokenizer(readLine())
        repeat(col) { j ->
            map[i][j] = st.nextToken().toInt()
        }
    }

    val ans = move(row, col, canMoveLikeHorse)
    if(ans == Integer.MAX_VALUE) println(-1)
    else println(ans)
}

private fun move(row: Int, col: Int, canMoveLikeHorse: Int): Int {
    val que: Queue<Monkey> = LinkedList()
    que.add(Monkey(0, 0, 0, canMoveLikeHorse))
    visited[0][0][canMoveLikeHorse] = true

    while(que.isNotEmpty()) {
        val cur = que.poll()
        val curY = cur.y
        val curX = cur.x
        val curCnt = cur.cnt
        val curCanHorse = cur.canMoveLikeHorse

        if(curY == row - 1 && curX == col - 1) return curCnt

        repeat(4) { i ->
            val nextY = curY + monkeyY[i]
            val nextX = curX + monkeyX[i]

            if(inRange(nextY, nextX, row, col) && !visited[nextY][nextX][curCanHorse] && map[nextY][nextX] == 0) {
                que.add(Monkey(nextY, nextX, curCnt + 1, curCanHorse))
                visited[nextY][nextX][curCanHorse] = true
            }
        }

        if(curCanHorse > 0) {
            repeat(8) { i ->
                val nextY = curY + horseY[i]
                val nextX = curX + horseX[i]

                if(inRange(nextY, nextX, row, col) && !visited[nextY][nextX][curCanHorse-1] && map[nextY][nextX] == 0) {
                    que.add(Monkey(nextY, nextX, curCnt + 1, curCanHorse - 1))
                    visited[nextY][nextX][curCanHorse - 1] = true
                }
            }
        }
    }

    return Integer.MAX_VALUE
}

private fun inRange(y: Int, x: Int, row: Int, col: Int): Boolean = (y in 0 until row && x in 0 until col)