[Python 3] BOJ 16973 직사각형 탈출

 

보통의 bfs와 같은 그래프 탐색 문제는 한 개의 지도를 바탕으로 1x1짜리 정사각형이 좌표를 돌아다니는 느낌인데, 이 문제는 우리가 움직여야 하는 직사각형의 크기가 H by W이다. 따라서, 직사각형을 움직이면서, 도착지점에 갈 수 있는 최소이동을 물어보는 문제였다.

 

BFS로 해결했다. 

처음 시작점에 직사각형이 위치할 수 있는지 여부를 확인한다.

이후 왼쪽 상단 지점을 기준으로 직사각형의 좌표를 잡고 상하좌우로 이동시킨다.

만약 벽이 있거나, 장애물이 있으면 움직일 수 없다.

하지만 단순히 이동한 직사각형 안의 모든 좌표를 확인해야하면 시간초과 (TLE)가 발생한다.

우리가 이미 검증했던 좌표들은 사실 다시 확인할 필요가 없다.

즉, 상하좌우 이동에서 방문하게 되는 새로운 좌표들에서만 장애물 여부를 확인하면 된다.

 

 

예를 들어, 파란색 네모가 빨간색 으로 이동하고 싶다. 그렇다면, 이런식으로 노란색으로 칠한 새롭게 방문하는 부분만 확인하면 된다는 뜻이다.

from collections import deque
n,m=map(int,input().split())
data=list(list(map(int,input().split())) for _ in range(n))
h,w,startx,starty,endx,endy=map(int,input().split())
startx-=1
starty-=1
endx-=1
endy-=1
q=deque()
visited=list(list(0 for _ in range(m-w+1)) for _ in range(n-h+1))

for i in range(startx,startx+h):
    for j in range(starty,starty+w):
        if data[i][j]:
            print(-1)
            exit(0)
visited[startx][starty]=1
q.append([startx,starty,[]])

dx=[-1,1,0,0]
dy=[0,0,-1,1] #u,d, l,r

while q:
    x,y,directions=q.popleft()
    if x==endx and y==endy:
        print(len(directions))
        exit(0)
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if not (0<=nx<=n-h and 0<=ny<=m-w):
            continue
        if visited[nx][ny]:
            continue
        flag=0
        if i==0:
            for k in range(w):
                if data[x-1][y+k]:
                    flag=1
                    break
        elif i==1:
            for k in range(w):
                if data[x+h][y+k]:
                    flag=1
                    break
        
        elif i==2:
            for k in range(h):
                if data[x+k][y-1]:
                    flag=1
                    break
        else:
            for k in range(h):
                if data[x+k][y+w]:
                    flag=1
                    break
        
        if not flag:
            visited[nx][ny]=1
            q.append([nx,ny,directions+[i]])
print(-1)