[BOJ 16973] 직사각형 탈출 - Python 풀이

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

 

문제

크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자.

격자판의 각 칸에는 빈 칸 또는 벽이 있다. 직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자판을 벗어날 수 없다.

직사각형은 한 번에 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 한 칸 이동시킬 수 있다.

입력

첫째 줄에 격자판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 각 칸의 정보가 주어진다. 0은 빈 칸, 1은 벽이다.

마지막 줄에는 직사각형의 크기 H, W, 시작 좌표 Sr, Sc, 도착 좌표 Fr, Fc가 주어진다.

격자판의 좌표는 (r, c) 형태이고, r은 행, c는 열이다. 1 ≤ r ≤ N, 1 ≤ c ≤ M을 만족한다.

출력

첫째 줄에 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

제한

• 2 ≤ N, M ≤ 1,000
• 1 ≤ H ≤ N
• 1 ≤ W ≤ M
• 1 ≤ Sr ≤ N-H+1
• 1 ≤ Sc ≤ M-W+1
• 1 ≤ Fr ≤ N-H+1
• 1 ≤ Fc ≤ M-W+1
• 입력으로 주어진 직사각형은 격자판을 벗어나지 않고, 직사각형이 놓여 있는 칸에는 벽이 없다.

예제 입력 1

4 5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
2 2 1 1 1 4

예제 출력 1

7

아래, 아래, 오른쪽, 오른쪽, 오른쪽, 위, 위

 

코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
grid = [[0] * (M+1)]
for _ in range(N):
    grid.append([0] + list(map(int, sys.stdin.readline().split())))
H, W, x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
visited = [[False] * (M+1) for _ in range(N+1)]
prefix = [[0] * (M+1) for _ in range(N+1)]
result = 0

# prefix 배열을 초기화하는 함수
def init_prefix():
    for i in range(1, N+1):
        for j in range(1, M+1):
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + grid[i][j]

def in_range(x, y):
    return 1 <= x < N+1 and 1 <= y < M+1

# x1, y1: 직사각형의 왼쪽 최상단
# x2, y2: 직사각형의 오른쪽 최하단
# x1, y1 부터 x2, y2의 합을 구하여 이 안에 벽이 있는지 확인하는 함수
def get_prefix(x1, y1, x2, y2):
    return prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]

# x, y가 새로운 좌표로 이동할 수 있는지 체크하는 함수
def can_go(x1, y1, x2, y2):
    if not in_range(x1, y1): return False
    if not in_range(x2, y2): return False
    if visited[x1][y1]: return False
    if get_prefix(x1, y1, x2, y2) > 0: return False
    return True


def bfs():
    global result

    q = deque()
    visited[x1][y1] = True
    q.append((x1, y1, 0))
    dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]

    while q:
        # x: x좌표
        # y: y좌표
        # z: 이동횟수
        x, y, z= q.popleft()

        # 도착지점 도착시 result에 이동횟수 저장 후 while문 탈출
        if x == x2 and y == y2: 
            result = z
            break

        for i in range(4):
            new_x, new_y = x+dx[i], y+dy[i]
            # new_x, new_y: x,y로부터 dx[i], dy[i] 방향으로 이동한 후 만들어지는 직사각형의 왼쪽 최상단
            # new_x+H, new_y+W: x,y로부터 dx[i], dy[i] 방향으로 이동한 후 만들어지는 직사각형의 오른쪽 최하단
            if can_go(new_x, new_y, new_x+(H-1), new_y+(W-1)):
                # 방문체크는 왼쪽 최상단만
                visited[new_x][new_y] = True
                q.append((new_x, new_y, z+1))

init_prefix()
bfs()
print(result if visited[x2][y2] else -1)

 

 

결과

 

풀이

BFS + Prefix 문제였다.

BFS는 딱히 특별할건 없고, 벽이 있는지를 체크하기 위해 Prefix를 사용한다는 점이 이 문제의 관건이다.

이중 for문을 사용해서 확인할 수도 있지만, H,W 값이 커질 경우 새로운 좌표로 이동할 수 있는지 체크할 때마다 H*W번의 연산을 해줘야 하기 때문에 비효율적이므로, 초반에 Prefix를 구하고 새로운 좌표인 new_x, new_y ~ new_x+(H-1), new_y+(W-1)의 Prefix값을 구하는 것이 좋다.

로직이 어렵진 않았으나 좌표를 조작하는 것에서 실수가 있어서 시간을 잡아먹었다.