[PG/Python] 아이템 줍기

📌 문제

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

코딩테스트 연습 - 아이템 줍기

 

📌 문제 접근 방법

1. 사각형의 테두리와 테두리를 제외한 내부의 점들의 좌표를 각각 border와 inner에 저장하였다.
2. border에 좌표를 저장할 때는 다른 사각형의 내부에 있는 경우를 제외해야 하므로 inner에 없는 좌표만 저장한다.
3. inner에 좌표를 저장할 때는 이미 border에 들어가있는 좌표 중 사각형 내부와 겹친다면 제거해줘야 하므로 border에 들어가있는지 확인을 해준다.
4. 그리고 캐릭터의 위치를 시작점으로 bfs 탐색을 하여 아이템의 위치에 도착하면 거리를 return해준다.
5. 이 때, 좌표만 저장을 해줬기 때문에 실제로 연결된 점이 아닌데 탐색을 하는 경우가 생겼다. (그림 참고)
   

   

    
6. 이를 해결해주기 위해서 모든 좌표를 2배로 늘려주고 return할 때 저장된 거리에서 2를 나누어서 반환해줬다.

 

📌 코드

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    border = set()
    inner = set()
    
    for lx, ly, rx, ry in rectangle:
        # 가로
        for x in range(lx*2, rx*2+1):
            for y in [ly*2, ry*2]:
                if (x, y) not in inner:
                    border.add((x, y))
        
        # 세로
        for y in range(ly*2, ry*2+1):
            for x in [lx*2, rx*2]:
                if (x, y) not in inner:
                    border.add((x, y))
        
        for x in range(lx*2+1, rx*2):
            for y in range(ly*2+1, ry*2):
                if (x, y) in border:
                    border.remove((x, y))
                inner.add((x, y))
    
    queue = deque()
    queue.append((characterX*2, characterY*2, 0))
    
    border.remove((characterX*2, characterY*2))
    
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    while queue:
        x, y, dist = queue.popleft()
        if x == itemX*2 and y == itemY*2:
            return dist//2
        
        for dx, dy in dxy:
            nx, ny = x+dx, y+dy
            
            if (nx, ny) in border:
                border.remove((nx, ny))
                queue.append((nx, ny, dist+1))