[프로그래머스 아이템줍기] (파이썬)

💡 문제 해결 아이디어

• 네모들의 테두리는 1로, 네모들의 내부는 0으로 채우면 되지않을까???

1차 시도, 그러나... 

🛠️ 피드백 아이디어

• 위의 사진 중 우측을 보면 문제가 있다.
• 빨간색부분이 우리가 의도한 테두리이나, 알고리즘은 주황색에서 어느 쪽이 의도한 테두리인지를 모른다.
• 그럼 어떡하지...? 한 칸 띄우자! 맵을 두배로 만들어서!

더이상 코드가 헷갈리지 않을것이다!

💻 작성된 코드

import numpy as np

def solution(rectangle, characterX, characterY, itemX, itemY):
    # 매트릭스를 0으로 초기화 (50의 2배인 100+1로)
    matrix = np.zeros((101, 101))
    
    # 사각형들을 10001로 채운다 (가능한 최대거리 + 1)
    for x1, y1, x2, y2 in rectangle:
        matrix[y1*2:y2*2+1, x1*2:x2*2+1] = 10001
        
    # 사각형의 내부를 0으로 채운다.
    for x1, y1, x2, y2 in rectangle:
        matrix[y1*2+1:y2*2,x1*2+1:x2*2] = 0

    # 큐에 초기 위치와 거리를 넣는다.
    q = [[characterY*2, characterX*2, 0]]

    # BFS를 수행한다!
    while q:
        y, x, dist = q.pop(0)
        # 이미 온적 있는 곳이라면, 아래 과정을 건너뛴다.
        if matrix[y][x] <= dist:  
            continue
        # 아이템 위치에 도달했다면, 거리를 return
        if y == itemY*2 and x == itemX*2:
            return dist//2
        matrix[y][x] = dist  # 방문한 좌표에 거리를 기록
        wasd = [[y+1, x], [y-1, x], [y, x+1], [y, x-1]]  # 가능한 이동의 경우들.
        for y, x in wasd:
            # 맵에서 벗어나지 않는지, 사각형 테두리가 맞는지 확인.
            if 0 <= y < 101 and 0 <= x < 101 and matrix[y][x] != 0:  
                # 큐에 해당 좌표를 추가.
                q.append([y, x, dist+1])