[프로그래머스] 아이템 줍기 - 파이썬/BFS

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

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    maxX = 0
    maxY = 0
    for x,y,x2,y2 in rectangle:
        maxX = max(x2 * 2,maxX)
        maxY = max(y2 * 2,maxY)

    graph = [[0] * (maxX + 2) for _ in range(maxY + 2)]
    for x,y,x2,y2 in rectangle:
        for j in range(x*2, (x2*2) + 1):
            for k in range(y*2, (y2*2) + 1):
                graph[k][j] = 1

    for y in range(1,maxY + 1):
        for x in range(1,maxX + 1):
            for i in range(3):
                for j in range(3):
                    if graph[y + i - 1][x + j - 1] == 0 and graph[y][x] == 1:
                        graph[y][x] = 2
                        break

    q = deque([(characterX*2,characterY*2,0)])

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    while q:

        x,y,cnt = q.popleft()
        graph[y][x]=1
        if (x,y) == (itemX*2,itemY*2):
            answer = int(cnt/2)
            break

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if graph[ny][nx]==2:
                q.append((nx,ny,cnt+1))

    return answer


rectangle = [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]]

solution(rectangle,9,7,6,1)

주변 8방향에서 하나라도 빈 공간 값이 있다면 테두리로 취급한다.

테두리를 먼저 구하고 BFS로 두 점 사이의 길이를 구한다.

중요한 점은 길이를 두배로하여 문제를 풀고 다시 절반으로 줄이는 것이다.

길이를 두배로 늘리는 이유는 다음과 같다.

이 부분은 좌표로

1 1
1 1

인데

이러한 케이스와 구분이 안가기 때문이다.

그렇기때문에 길이를 두배로해줘 이러한 케이스가 발생하는 것을 방지한다.