문제 설명

제한 사항

입출력 예

구현 아이디어

처음에는 테두리에 해당하는 정수 좌표들을 리스트에 담고 BFS로 최단거리를 찾고자 했다.
하지만 리스트를 만드는 과정부터 코드가 매우 길어져 다른 분들의 코드를 참고하여 문제를 다시 풀었다.

1. 2차원 리스트를 만들어 테두리는 1, 사각형 내부는 0으로 채운다.
2. BFS로 최단거리를 찾는다.

좌표를 2차원 리스트로 옮기는 것은 위 그림처럼 할 수 있다.
(1, 1), (2, 1) ... 각 좌표를 한 칸이라고 생각하면 된다.

주의해야 할 점

테두리를 따라서 가는 경로 중 (3,5) → (4,5) → (4,6) → (3,6)으로 가는 것이 테두리를 따라서 가는 올바른 경로이다.

하지만 위와 같은 이차원 리스트에서 BFS를 진행하면, (3,5) → (4,5)가 아닌 (3,5) → (3,6)을 선택하게 된다 !

이를 방지하기 위해서 이차원 리스트 좌표, 캐릭터의 좌표, 아이템의 좌표를 2배씩 해주어 BFS를 진행한다.
그러면 최단 거리도 2배만큼이 나올 것이고, 최종적으로 답을 반환할 때 나누기 2를 해주어 반환하면 된다.

전체 코드

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    graph = [[-1 for _ in range(102)] for _ in range(102)]
    visited = [[1 for _ in range(102)] for _ in range(102)]
    direction = [(0, -1), (1, 0), (0, 1), (-1, 0)]
    dq = deque()
    
    for r in rectangle:
        x1, y1, x2, y2 = map(lambda x: x*2, r)
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                # x1, x2, y1, y2는 테두리이므로 제외하고 내부만 0으로 채움
                if x1 < i < x2 and y1 < j < y2:
                    graph[i][j] = 0
                # 다른 직사각형의 내부가 아니면서 테두리일 때 1로 채움
                elif graph[i][j] != 0:
                    graph[i][j] = 1                
    # 반복문을 마치면 테두리는 1, 내부는 0, 외부는 -1이 될 것이다   
    
    # 캐릭터와 아이템의 좌표도 2배씩 늘린다
    cx, cy, ix, iy = 2*characterX, 2*characterY, 2*itemX, 2*itemY
    
    dq.append((cx, cy))
    
    while dq:
        x, y = dq.popleft()
        
        if x == ix and y == iy:
        	# 답을 반환할 때 2로 나누어 반환해준다
            answer = visited[x][y] // 2
            break   
        for k in range(4):
            nx, ny = x + direction[k][0], y + direction[k][1]
            
            if graph[nx][ny] == 1 and visited[nx][ny] == 1:
                visited[nx][ny] += visited[x][y]
                dq.append((nx, ny))

    return answer