[백준 1600번] [Kotlin] 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

 

 

난이도 : 골드 3
태그 : 그래프 탐색, 그래프 이론, 너비 우선 탐색

 

 

설명

이전에 많이 해보았던 상하좌우 4방향으로 이동하는 BFS 문제에,

체스의 나이트 방향으로 움직일 수 있는 조건이 더해진 문제입니다.

 

단, 나이트 이동의 경우 k번이라는 제약조건이 있으므로,

말 이동을 k번 이하로 사용하면서 최단 경로로 목표지점에 도달하는게 핵심입니다.

 

 

 

소스코드

Data Class - Point, dx & dy

data class Point(var x: Int, var y: Int, var d: Int, var k: Int)

 

Point는 x, y, 이동한 횟수(d), 말로 이동한 횟수(k)를 담을 data class 입니다.

 

val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)
val hx = arrayOf(-2, -2, 2, 2, 1, -1, 1, -1)
val hy = arrayOf(1, -1, 1, -1, 2, 2, -2, -2)

 

dx, dy는 상하좌우 이동을 할때 쓰이며,

hx, hy는 말 이동을 할때 쓰입니다.

 

 

인풋값 세팅

val br = BufferedReader(InputStreamReader(System.`in`))
val k = br.readLine().toInt()
val wh = br.readLine().split(" ")

val w = wh[0].toInt()
val h = wh[1].toInt()

val map = Array(h) { Array(w) { 0 } }

repeat(h) { x ->
    val st = StringTokenizer(br.readLine(), " ")
    repeat(w) { y -> map[x][y] = st.nextToken().toInt() }
}

 

 

흔히 세로길이 - 가로길이 순으로 주어지지만,

본 문제에서는 가로길이(w)가 먼저, 세로길이(h)가 나중에 주어집니다.

 

 

BFS

val q: Queue<Point> = LinkedList()
val visited = Array(h) { Array(w) { Array(k + 1) { false } } }

// 맨 왼쪽 위 -> 맨 오른쪽 아래
q.offer(Point(0, 0, 0, 0))
visited[0][0][0] = true

while (q.isNotEmpty()) {
    val target = q.poll()
    val tx = target.x
    val ty = target.y
    val tk = target.k
    val td = target.d

    if (tx == h - 1 && ty == w - 1) {
        println(td)
        return
    }

    // 상하좌우
    for (i in 0 until 4) {
        val nx = tx + dx[i]
        val ny = ty + dy[i]

        if (nx !in 0 until h || ny !in 0 until w || visited[nx][ny][tk] || map[nx][ny] == 1) continue
        q.offer(Point(nx, ny, td + 1, tk))
        visited[nx][ny][tk] = true
    }

    // knight 처럼 움직임
    if (tk < k) {
        for (i in 0 until 8) {
            val nx = tx + hx[i]
            val ny = ty + hy[i]
            val nk = tk + 1

            if (nx !in 0 until h || ny !in 0 until w || visited[nx][ny][nk] || map[nx][ny] == 1) continue
            q.offer(Point(nx, ny, td + 1, nk))
            visited[nx][ny][nk] = true
        }
    }
}

 

BFS를 수행하는 부분입니다.

 

말 이동을 k번째 했을때의 상태를 저장하기 위해,

visited 배열을 3차원 형태로, h,w, k + 1크기만큼 만듭니다.

 

이후, 일반 이동(상하좌우)와 나이트이동(8방향) 각각에 대해 처리하고,

나이트 이동의 경우 k를 1씩 증가해 처리합니다.

 

단, 나이트 이동은 최대 k번만 할 수 있으므로 tk < k일때만 수행합니다.

 

 

 

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

data class Point(var x: Int, var y: Int, var d: Int, var k: Int)

fun main() {

    val dx = arrayOf(0, 0, 1, -1)
    val dy = arrayOf(1, -1, 0, 0)
    val hx = arrayOf(-2, -2, 2, 2, 1, -1, 1, -1)
    val hy = arrayOf(1, -1, 1, -1, 2, 2, -2, -2)


    val br = BufferedReader(InputStreamReader(System.`in`))
    val k = br.readLine().toInt()
    val wh = br.readLine().split(" ")

    val w = wh[0].toInt()
    val h = wh[1].toInt()

    val map = Array(h) { Array(w) { 0 } }

    repeat(h) { x ->
        val st = StringTokenizer(br.readLine(), " ")
        repeat(w) { y -> map[x][y] = st.nextToken().toInt() }
    }

    val q: Queue<Point> = LinkedList()
    val visited = Array(h) { Array(w) { Array(k + 1) { false } } }

    // 맨 왼쪽 위 -> 맨 오른쪽 아래
    q.offer(Point(0, 0, 0, 0))
    visited[0][0][0] = true

    while (q.isNotEmpty()) {
        val target = q.poll()
        val tx = target.x
        val ty = target.y
        val tk = target.k
        val td = target.d

        if (tx == h - 1 && ty == w - 1) {
            println(td)
            return
        }

        // 상하좌우
        for (i in 0 until 4) {
            val nx = tx + dx[i]
            val ny = ty + dy[i]

            if (nx !in 0 until h || ny !in 0 until w || visited[nx][ny][tk] || map[nx][ny] == 1) continue
            q.offer(Point(nx, ny, td + 1, tk))
            visited[nx][ny][tk] = true
        }

        // knight 처럼 움직임
        if (tk < k) {
            for (i in 0 until 8) {
                val nx = tx + hx[i]
                val ny = ty + hy[i]
                val nk = tk + 1

                if (nx !in 0 until h || ny !in 0 until w || visited[nx][ny][nk] || map[nx][ny] == 1) continue
                q.offer(Point(nx, ny, td + 1, nk))
                visited[nx][ny][nk] = true
            }
        }
    }

    println(-1)
}

 

후기

 

다른 문제들과 다르게, 가로길이 세로길이가 반대 순서로 주어져 엉뚱한 곳에서 시간을 끌고,

3차원 visited 없이 2차원 visited 배열과 Point 데이터 클래스 만으로 해결할 수 있다 생각하여

꽤 많은 시간을 들이고, 꽤 많은 '틀렸습니다' 를 받은 끝에 풀은 문제입니다.

 

마침내 나이트 이동이 0번, 1번, 2번, 3번 ... k번 각각 저장해야 함을 깨닫고

3차원 visited를 사용해 우여곡절 끝에 풀었던 문제였네요 ㅎㅎ...