[BOJ 16973 🥇4] 직사각형 탈출 (Python)

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

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

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

 

예제 입력 2 

6 7
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0
0 0 0 0 0 0 0
2 3 1 1 5 5

 

예제 출력 2

8

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

 

⭕ CODE

from collections import deque

# 이동한 직사각형 내에 벽이 존재하는지 체크하기 위한 함수
def check(x, y):
    flag = True
    for a, b in wall:
        if x <= a < x + h and y <= b < y + w:
            flag = False
            break
    return flag


dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

n, m = map(int, input().split())

arr = [list(map(int, input().split())) for _ in range(n)]

# 벽을 체크하기 위한 리스트
wall = []
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            wall.append((i, j))

h, w, sx, sy, fx, fy = map(int, input().split())

# 방문표시
visited = [[0] * m for _ in range(n)]

q = deque()

# 직사각형의 가장 왼쪽 위칸만 조사
q.append((sx - 1, sy - 1))

# 방문 처리
visited[sx - 1][sy - 1] = 1

# 도착했는지 확인하기 위한 flag
flag = 0

while q:
    x, y = q.popleft()

    # 최종 도착지에 도착한다면
    if x == fx - 1 and y == fy - 1:
        # 최소 이동 횟수 출력하고 flag = 1 즉 도착함
        print(visited[x][y] - 1)
        flag = 1
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # 다음 이동 위치가 격자 안에 존재하고
        # 직사각형 또한 격자 안에 존재한다면
        if 0 <= nx < n and 0 <= ny < m and 0 <= nx + h - 1 < n and 0 <= ny + w - 1 < m:
            # 방문한적이 없고
            if visited[nx][ny] == 0:
                # 이동하는 직사각형 내에 벽이 존재하는지 체크
                if check(nx, ny):
                    # 이동 횟수 증가
                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx, ny))

# 만약 이동할 수 없는 경우에는 -1을 출력
if flag == 0:
    print(-1)

✏️ Comment

처음에는 왼쪽 위의 꼭지점을 잡고 check하는 과정에서 모든 직사각형 내에 벽이 존재하는지를  판단하였는데 시간초과가 나왔다. 직사각형의 범위가 최대로 가면 1000*1000인데 그 과정에서 많은 시간이 걸렸다고 생각한다.

다른 방법이 무엇이 있을까 고민하다가 벽이 직사각형 내부에 존재하면 불가능하다고 판별하였더니 시간초과 문제가 해결되었다.

 

• 조건을 여러 방향에서 고민하자