[BOJ] BOJ 16974 직사각형 탈출 Python

www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

1. 문제

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

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

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

2. 입력

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

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

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

3. 출력

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

4. 제한

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

 

5. 풀이

Python3로 돌리면 시간초과가 발생한다. 따라서 Pypy 이용할 것!

import sys

input = sys.stdin.readline
N, M = map(int, input().split())

MAP = []
for _ in range(N):
    row = list(map(int, input().split()))
    MAP.append(row)

H, W, Sr, Sc, Fr, Fc = map(int, input().split())

#좌표 시작 기준점이 1,1 이므로 1씩 빼준다. 
Sr, Sc, Fr, Fc = Sr-1, Sc-1, Fr-1, Fc-1 

#발견 여부를 기록할 리스트
visited = [[0 for i in range(M)] for i in range(N)]

#직사각형 내부에 벽이 있으면 안되므로 벽 위치를 기록해준다.
walls =[]
for row in range(N):
    for col in range(M):
        if MAP[row][col] ==1:
            walls.append((row,col,))
            
#새롭게 이동된 시작으로 직사각형이 움직일 수 있는지 없는지를 판단
def isSatisfied(nrow, ncol):
	
    #이동한 시작점을 기준으로 했을 때 직사각형이 맵 밖으로 넘어가면 안된다.
    if nrow + H -1 >= N or ncol + W -1 >= M:
        return False

	#직사각형 내부에 벽이 있으면 안된다.
    for w_row, w_col in walls:
        if nrow <= w_row < nrow + H and ncol <= w_col < ncol + W:
            return False
    return True


#BFS
def bfs():
    queue =[]
    #직사각형의 시작점과 이동 횟수를 넣어준다.
    queue.append((0, Sr, Sc))
    
    #큐가 빌때까지
    while queue:
    	#큐에서 한개씩 빼서 확인한다.
        path, row, col = queue.pop(0)
		
        #문제에서 제시한 도착지점에 도착하면 이동 횟수를 반환
        if row == Fr and col == Fc:
            return path
            
		#이동방향은 아래, 위, 왼쪽, 오른쪽        
        for drow, dcol in [[-1, 0],[1,0],[0,-1],[0,1]]:
            nrow = row + drow
            ncol = col + dcol
			
            #해당 시작점이 맵 밖으로 벗어나는 경우
            if nrow < 0 or nrow >= N or ncol < 0 or ncol >= M:
                continue
			
            #직사각형 구속조건
            if not isSatisfied(nrow, ncol):
                continue
			
            #위 두조건을 만족시키지 않으면서 방문하지 않았다면
            if not visited[nrow][ncol]:
                visited[nrow][ncol] = 1 #체크해주고
                queue.append((path+1, nrow, ncol)) #큐에 넣어준다.

    return -1

print(bfs())