백준 2194 유닛 이동시키기 Kotlin (bfs)

문제 출처 : https://www.acmicpc.net/problem/2194

2194번: 유닛 이동시키기

문제

스타크래프트와 같은 게임을 하다 보면 어떤 유닛을 목적지까지 이동시켜야 하는 경우가 종종 발생한다. 편의상 맵을 N×M 크기의 2차원 행렬로 생각하자. 또한 각각의 유닛은 크기를 가질 수 있는데, 이를 A×B 크기의 2차원 행렬로 생각하자. 아래는 5×5 크기의 맵과 2×2 크기의 유닛에 대한 한 예이다. S는 시작점을 나타내며 E는 끝점을 나타낸다.

유닛은 상하좌우의 네 방향으로만 움직일 수 있다. 단, 유닛의 일부분이 장애물이 설치된 부분(위의 예에서 색이 칠해진 부분)을 지날 경우, 위의 예에서는 시작 위치에서 위로 이동하는 경우는 허용되지 않는다. 위의 예는 유닛을 오른쪽으로 세 칸, 위쪽으로 세 칸 움직이면 목적지에 도달할 수 있고, 이 경우가 가장 적은 이동 회수를 거치는 경우이다. 이동하는 도중에 유닛이 맵 밖으로 나가는 경우는 허용되지 않는다.

맵의 정보와 유닛의 정보가 주어졌을 때, 유닛을 목적지까지 움직이기 위해 필요한 최소의 이동 회수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 다섯 개의 정수 N, M(1 ≤ N, M ≤ 500), A, B(1 ≤ A, B ≤ 10), K(0 ≤ K ≤ 100,000)가 주어진다. 다음 K개의 줄에는 장애물이 설치된 위치(행 번호, 열 번호)가 주어진다. 그 다음 줄에는 시작점의 위치와 도착점의 위치가 주어진다. 시작점의 위치와 도착점의 위치는 제일 왼쪽 제일 위의 한 점만 주어진다. 시작점의 위치와 도착점의 위치는 같지 않다.

출력

첫째 줄에 답을 출력한다. 이동이 불가능한 경우에는 -1을 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

이동 시키는 노드의 크기가 A*B인 것 빼고는 기본적인 BFS 문제와 다를 게 없다.

따라서 일단 A*B 크기라는 것을 생각하지 말고 기본적인 BFS 로직을 구현한 후, A*B에 대해 구현하면 된다.

기존엔 visited[nextR][nextC]가 true 라면 (검사할 한 칸을 이미 방문했다면) 스킵했다면,

nextR,nextC 좌표는 움직일 노드의 가장 왼쪽 가장 위의 한 좌표이므로, nextR, nextC에서 시작해서 A*B만큼의 사이즈를 검사해 nextR,nextC로 움직일 수 있는지 체크해야 한다.

따라서 기존에 if(visited[nextR][nextC]) continue 로 이미 방문한 칸을 스킵했다면

if(!checkCanMove(nextR,nextC,n,m,a,b)) continue 와 같이 바꿀 수 있고, 아래 checkCanMove만 구현해주면 된다.

fun checkCanMove(sr: Int, sc: Int, a: Int, b: Int, n: Int, m: Int): Boolean {
    for (r in sr until sr + a) {
        if (r !in 0 until n) return false
        for (c in sc until sc + b) {
            if (c !in 0 until m) return false
            if (graph[r][c] == 2) return false
        }
    }
    return true
}

주의할 점은 graph를 Boolean으로 두고 방문한 칸과 벽을 모두 false로 정의하면 위 로직에선 A*B 사이즈를 검사할 때 이미 방문한 칸이라고 인식되어 버린다.

따라서 벽을 2로, 방문한 칸을 1로, 아직 방문하지 않은 칸을 0으로 구분해주었다. 

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()
lateinit var graph: Array<IntArray>
val dir = arrayOf(
    arrayOf(0, 1),
    arrayOf(1, 0),
    arrayOf(0, -1),
    arrayOf(-1, 0)
)

data class Node(
    val r: Int,
    val c: Int,
    val cnt: Int,
)

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n, m, a, b, k) = getIntList()
    graph = Array(n) { IntArray(m) }
    repeat(k) {
        val (r, c) = getIntList()
        graph[r - 1][c - 1] = 2
    }
    val (sr, sc) = getIntList()
    val (er, ec) = getIntList()
    write("${bfs(n, m, a, b, sr - 1, sc - 1, er - 1, ec - 1)}")
    close()
}

fun bfs(n: Int, m: Int, a: Int, b: Int, sr: Int, sc: Int, er: Int, ec: Int): Int {
    val q: Queue<Node> = LinkedList()
    q.add(Node(sr, sc, 0))
    graph[sr][sc] = 1
    while (q.isNotEmpty()) {
        val (cr, cc, cCnt) = q.poll()
        for (i in 0 until 4) {
            val nr = cr + dir[i][0]
            val nc = cc + dir[i][1]
            val nCnt = cCnt + 1
            if (nr !in 0 until n || nc !in 0 until m) continue
            if (graph[nr][nc] != 0) continue
            if (!checkCanMove(nr, nc, a, b, n, m)) continue
            if (nr == er && nc == ec) return nCnt
            q.add(Node(nr, nc, nCnt))
            graph[nr][nc] = 1
        }
    }
    return -1
}

fun checkCanMove(sr: Int, sc: Int, a: Int, b: Int, n: Int, m: Int): Boolean {
    for (r in sr until sr + a) {
        if (r !in 0 until n) return false
        for (c in sc until sc + b) {
            if (c !in 0 until m) return false
            if (graph[r][c] == 2) return false
        }
    }
    return true
}