[백준 16973번] [Kotlin] 직사각형 탈출

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

16973번: 직사각형 탈출

 

난이도 : 골드 4
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 누적 합

 

 

설명

직사각형이 장애물에 걸리지 않게 시작점에서 도착점으로 갈 수 있는지 판단하는 문제입니다.

 

처음에는 BFS를 돌리며 각 좌표마다 직사각형의 넓이만큼 맵을 확인하는 방법으로 풀었으나, 시간초과를 맞이했습니다

 

어떻게 할까 고민을 하다가, 맵에 미리 장애물의 크기를 매핑해놓자고 생각했습니다.

 

문제에서 직사각형의 맨 왼쪽 위 꼭짓점 좌표가 주어지므로,

두 번째 그림과 같이 각 장애물마다 직사각형의 가로, 세로만큼 확장을 시켜줍니다

 

 

 

예제 2번도 두 번째 그림과 같이 직사각형의 가로, 세로만큼 확장을 시킬 수 있습니다.

연한 파랑 -> 원래 장애물, 진한 파랑 -> 확장된 장애물

초록 -> 출발, 주황 -> 도착점 입니다.

 

 

 

이제 문제는 없을 줄 알았으나... 틀렸습니다를 받았습니다.

질문게시판에서 반례 여러 개를 찾아 돌려보니, 조금 알 것 같습니다.

 

위와 같은 상황에서, 정사각형의 크기가 3 * 3이라면 어떻게 될까요?

 

직사각형의 크기가 맵 경계를 벗어나기 때문에 무슨 짓을 해도 도착점에 도달하지 못합니다.

 

 

따라서, 장애물을 직사각형 크기만큼 확장시켰듯이,

오른쪽과 아래 벽을 직사각형 크기만큼 확장시켜줘야 합니다.

 

이제 확장된 새 맵을 토대로 BFS 탐색을 진행하면 됩니다.

 

 

 

소스코드

import java.util.LinkedList
import java.util.Queue
import java.util.StringTokenizer

class Node(val x: Int, val y: Int)

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    val map = Array(n) { readLine().split(" ").map { it.toInt() }.toIntArray() }

    val st = StringTokenizer(readLine())
    val (h, w) = List(2) { st.nextToken().toInt() }
    val (startX, startY, endX, endY) = List(4) { st.nextToken().toInt() - 1 }

    if (startX == endX && startY == endY) {
        println(0)
        return@with
    }

    for (x in 0..<n) {
        for (y in 0..<m) {
            if (map[x][y] == 0) continue
            for (dh in 0..<h) {
                for (dw in 0..<w) {
                    val nx = x - dh
                    val ny = y - dw
                    if (nx !in 0..<n || ny !in 0..<m) continue
                    map[nx][ny] = 1
                }
            }
        }
    }

    for (i in n - h + 1..<n) {
        for (j in 0..<m) {
            map[i][j] = 1
        }
    }


    for (i in 0..<n) {
        for (j in m - w + 1..<m) {
            map[i][j] = 1
        }
    }

    val visited = Array(n) { IntArray(m) }
    val dx = intArrayOf(0, 0, 1, -1)
    val dy = intArrayOf(1, -1, 0, 0)
    val q = LinkedList<Node>() as Queue<Node>

    q.offer(Node(startX, startY))
    visited[startX][startY] = 1

    while (q.isNotEmpty()) {
        val cur = q.poll()

        next@ for (i in 0..<4) {
            val nx = cur.x + dx[i]
            val ny = cur.y + dy[i]

            if (nx !in 0..<n || ny !in 0..<m || visited[nx][ny] != 0 || map[nx][ny] == 1) continue@next

            if (nx == endX && ny == endY) {
                println(visited[cur.x][cur.y])
                return@with
            }

            q.offer(Node(nx, ny))
            visited[nx][ny] = visited[cur.x][cur.y] + 1
        }
    }

    println(-1)
}

 

 

 

후기

직사각형의 크기만큼 장애물을 확장시키자! 라는 아이디어는 빠르게 떠올렸으나

오른쪽 벽과 아래 벽을 고려하지 못해 다소 시간이 걸렸습니다.