[Python/파이썬]프로그래머스 87694. 아이템 줍기

https://school.programmers.co.kr/learn/courses/30/lessons/87694

프로그래머스

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    # 좌표 확장
    board = [[-1] * 102 for _ in range(102)]
    for x1, y1, x2, y2 in rectangle:
        x1, y1, x2, y2 = x1*2, y1*2, x2*2, y2*2
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                if x1 < i < x2 and y1 < j < y2:
                    board[i][j] = 0  # 내부
                elif board[i][j] != 0:
                    board[i][j] = 1  # 테두리

    # BFS 초기화
    q = deque([(characterX*2, characterY*2, 0)])
    visited = set()
    visited.add((characterX*2, characterY*2))

    # 방향 벡터 (상, 하, 좌, 우)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # BFS 탐색
    while q:
        x, y, dist = q.popleft()
        if (x, y) == (itemX*2, itemY*2):
            return dist // 2  # 좌표를 2배 확장했으므로 실제 거리는 절반
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < 102 and 0 <= ny < 102 and board[nx][ny] == 1 and (nx, ny) not in visited:
                visited.add((nx, ny))
                q.append((nx, ny, dist + 1))

    return -1