[Python/파이썬] 백준 번 직사각형 탈출

 

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
• 입력으로 주어진 직사각형은 격자판을 벗어나지 않고, 직사각형이 놓여 있는 칸에는 벽이 없다.

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))
h, w, sr, sc, fr, fc = map(int, input().split())

# 누적합 계산
acc = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        acc[i][j] = acc[i-1][j]+acc[i][j-1]-acc[i-1][j-1]+board[i-1][j-1]

# 직사각형 범위 안에 벽이 있는지 확인
def wall_exist(r, c):
    if acc[r+h-1][c+w-1] - acc[r+h-1][c] - acc[r][c+w-1] + acc[r-1][c-1] > 0:
        return True
    else:
        return False


dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]
q = deque([(sr-1, sc-1, 0)])
visited = [[False]*m for _ in range(n)]
visited[sr-1][sc-1] = True
while q:
    r, c, cnt = q.popleft()
    if r == fr-1 and c == fc-1:
        print(cnt)
        exit()
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if nr >= 0 and nr+h-1 < n and nc >= 0 and nc+w-1 < m and not visited[nr][nc]:
            if acc[nr+h][nc+w]-acc[nr+h][nc]-acc[nr][nc+w]+acc[nr][nc] == 0:
                q.append((nr, nc, cnt+1))
                visited[nr][nc] = True
print(-1)

BFS+누적합을 이용하여 풀었다.

직사각형을 이동시켰을때 벽에 걸리는지 여부를 판단하기 위해 누적합을 사용하였다. 직사각형을 이동한 부분에 해당하는 누적합이 0 초과라면 이동한 부분에 벽이 있는 것이므로 이동시킬 수 없다.