from collections import deque
#사용의 편의성을 위해 deque를 import해준다
def solution(rectangle, characterX, characterY, itemX, itemY):
MAX = 102
#문제에서는 (50,50)의 공간이었지만 이렇게하면 자꾸 오류가 나는 것 같아 2배로 늘려준다. 근데 왜 오류가 나는지 까지는 잘 모르겠다
board = [[0] * MAX for _ in range(MAX)]
# 직사각형들도 2배 해준다
for x1, y1, x2, y2 in rectangle:
for x in range(x1*2, x2*2 + 1):
for y in range(y1*2, y2*2 + 1):
board[x][y] = 1
# 내부를 0으로 처리해준다. 외곽선만 남겨둔단 뜻이다
for x1, y1, x2, y2 in rectangle:
for x in range(x1*2 + 1, x2*2):
for y in range(y1*2 + 1, y2*2):
board[x][y] = 0
# BFS 준비
visited = [[False] * MAX for _ in range(MAX)]
q = deque()
q.append((characterX*2, characterY*2, 0))
visited[characterX*2][characterY*2] = True
#visited 이 부분까지가 초기 설정이다
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while q:
x, y, dist = q.popleft()
if x == itemX*2 and y == itemY*2:
return dist // 2 # 2배 했으니 return 할 때 나눠준다
for i in range(4): #거리를 탐색한다
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < MAX and 0 <= ny < MAX: #일단 MAX안에 있는지 확인
if board[nx][ny] == 1 and not visited[nx][ny]: #외곽선에 있는지도 확인한다
visited[nx][ny] = True
q.append((nx, ny, dist + 1))
return -1
