[백준 16973번] 파이썬 - 직사각형 탈출

백준 16973 - 직사각형 탈출

시간 제한 2초, 메모리 제한 512MB

# 조건

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

# 접근 방법

• 구현 문제이다.
• bfs를 수행하며 이동할 직사각형의 범위 내에 벽이 있는지 체크하면 된다.
• 이동할 때마다 check를 해준다면, 시간 초과가 발생할 것이다.
• 따라서, 벽은 이동하지 않으므로 시작할 때 미리 벽의 위치를 구해준 후, 해당 벽들이 범위 내에 있는지 판단만 해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def check(ci, cj):  
    for cr, cc in walls:  
        if ci<=cr<=ci+height-1 and cj<=cc<=cj+weight-1:  
            return False  
    return True  
def bfs():  
    q = deque()  
    q.append((sr-1, sc-1, 0))  
    visited[sr-1][sc-1] = True  

    while q:  
        si, sj, cnt = q.popleft()  
        if (si, sj) == (fr-1, fc-1):  
            print(cnt)  
            return  
        for d in range(4):  
            ni, nj = si + di[d], sj + dj[d]  
            if 0<=ni<N and 0<=nj<M and 0<=ni+height-1<N and 0<=nj+weight-1<M:  
                if not visited[ni][nj]:  
                    if check(ni, nj):  
                        visited[ni][nj] = True  
                        q.append((ni, nj, cnt+1))  
    print(-1)  
    return  

N, M = map(int, input().split())  
arr = [list(map(int, input().split())) for _ in range(N)]  
height, weight, sr, sc, fr, fc = list(map(int, input().split()))  
visited = [[False] * M for _ in range(N)]  
di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]  

walls = []  
for i in range(N):  
    for j in range(M):  
        if arr[i][j]:  
            walls.append((i, j))  

bfs()