[PS] 아이템 줍기

아이템 줍기

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    
    maps = [[0]*102 for _ in range(102)] # 두배로 늘리기
    visit = [[-1]*102 for _ in range(102)]

    for r in rectangle: 
        lx, ly, rx, ry = map(lambda x : x*2, r)
        for x in range(lx, rx+1) :
            for y in range(ly, ry+1): 
                if lx<x<rx and ly<y<ry: # 내부면 -1
                    maps[x][y] = -1
                elif maps[x][y] != -1:
                    maps[x][y] = 1
                    
    def bfs(x, y):
        visit[x][y] = 0
        queue = deque([(x, y)])
        
        dx = [-1,1,0,0]
        dy = [0,0,-1,1]
        
        while queue:
            x, y = queue.popleft()
            
            if x == itemX*2 and y == itemY*2:
                return visit[x][y]//2
            
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if 0<=nx<102 and 0<=ny<102:
                    if maps[nx][ny] == 1 and visit[nx][ny] == -1:
                        visit[nx][ny] = visit[x][y] + 1
                        queue.append((nx, ny))
            
        

    return bfs(characterX*2, characterY*2)

처음에는 두배로 늘리지 않고 풀었다.

이렇게 되면 길이(차이)가 1인 부분에 대해 바깥 테두리를 가지 않고 바로 뚫어버리는.. 문제가 발생한다. --> 이 부분을 어떻게 해결해야할 지 결국 몰라서 해답을 찾아봤다.
(자세한 설명 : https://jyeonnyang2.tistory.com/247)

따라서 모두 두배씩 해주고, 마지막 최단거리 값을 2로 나눠준다.