[프로그래머스] 아이템 줍기

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

이동 가능한 다음 위치를 결정하는게 좀 어려운 전형적인 BFS문제라고 생각했다.

캐릭터의 다음 위치(x, y) 가
i) 네모 안에 있거나
ii) 네모 경계에 있거나
iii) 네모 밖에 있거나
인데, 이걸 모든 네모에 대해 확인한다.

캐릭터가
어떤 네모 내부에 있거나,
모든 네모의 외부에 있으면
다음 위치가 될 수 없다.

처음에는 좌표 2배 안하고 제출했더니 실패하는 테스트케이스가 많았다.
그래서 냅다 클루드한테 물어봤더니

대각선 이동이 가능하게 되어 있다는 거임
대각선 이동이 뭔지 한참 생각했다ㅜ

왜 좌표 2배 이벤트가 필요한지 그림으로 그려보았다.

캐릭터가 초록색 루트로 이동하는 버그(?)가 있기 때문이다.
초록색 루트가 두 배가 되면 한 칸 단위로 움직이는 캐릭터는 더 이상 초록색 루트로는 이동할 수 없게 된다.

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):  
    rectangle = [[r * 2 for r in rect] for rect in rectangle]
    characterX, characterY, itemX, itemY = characterX * 2, characterY * 2, itemX * 2, itemY * 2
    
    def bfs():
        dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
        queue = deque([(characterX, characterY)])
        dist = {(characterX, characterY): 0}
        
        while queue:
            x, y = queue.popleft()
            
            if x == itemX and y == itemY:
                return dist[(x, y)] // 2  
            
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                
                if isValid(nx, ny):
                    if (nx, ny) not in dist:
                        dist[(nx, ny)] = dist[(x, y)] + 1
                        queue.append((nx, ny))
    
    def isValid(x, y):
        isvalid = False
        
        for rec in rectangle:
            x1, y1, x2, y2 = rec
            if x1 < x < x2 and y1 < y < y2:
                return False

            if (x == x1 or x == x2) and y1 <= y <= y2:
                isvalid = True
            elif (y == y1 or y == y2) and x1 <= x <= x2:
                isvalid = True

        return isvalid
        
    answer = bfs()
    return answer

참고
https://velog.io/@leeeeeyeon/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%95%84%EC%9D%B4%ED%85%9C-%EC%A4%8D%EA%B8%B0
Claude🤖