[Python] 아이템 줍기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87694?language=python3 

프로그래머스

 

---

해결 과정

캐릭터 위치에서 아이템 위치까지의 최단 경로를 구하는 것이기 때문에 BFS를 이용하여 풀었다.

여기서 주어진 직사각형의 간격이 1일 수 있음에 주의해야 한다. 예) rectangle = [1, 1, 2, 4] 
그렇게 되면 테두리가 아닌데도 캐릭터가 지나가게 되므로, 이 경우를 방지하기 위해 크기를 2배로 늘려주었다.
(물론 직사각형을 그릴 지형, 캐릭터 위치, 아이템 위치도 다 2배로 늘려주어야 한다.)

또한 직사각형을 지형에 그릴때에도 조금 고민했는데, 지형을 0으로 그리고 직사각형의 테두리는 1, 내부는 2로 그려주었다.
여기서 테두리를 그릴 때, 이미 2로 그려져있지 않아야 한다.
그 이유는 해당 위치가 현재 직사각형에서는 테두리라고 하더라도, 이전의 직사각형에서는 내부였기 때문이다.
=> 직사각형 겹치는 경우

 

---

코드

from collections import deque

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

def solution(rectangle, characterX, characterY, itemX, itemY):
    def bfs(x, y, count):
        queue = deque([[x, y, count]])  # 시작 위치 넣어주기 
        while queue:
            x, y, count = queue.popleft()   # 가볼 위치 좌표와 거리 가져오기 

            if x == itemX and y == itemY:   # 아이템에 도달한 경우 
                return count

            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                # 테두리를 따라 이동
                if 0 <= nx < 102 and 0 <= ny < 102 and board[ny][nx] == 1:   
                    board[ny][nx] = 2   # 갔던 곳 다시 못가게 방문처리 
                    queue.append([nx, ny, count + 1])

    # 직사각형 그리기 (간격이 1인 직사각형을 대비하여 두배로 늘려주기) 
    board = [[0 for _ in range(102)] for _ in range(102)]
    for rec in rectangle:
        lx, ly, rx, ry = map(lambda x: x * 2, rec)
        for x in range(lx, rx + 1):
            for y in range(ly, ry + 1):
                if lx < x < rx and ly < y < ry: # 직사각형의 내부인 경우 
                    board[y][x] = 2
                elif board[y][x] != 2:  # 직사각형의 테두리이고, 다른 직사각형의 내부가 아닌 경우 
                    board[y][x] = 1

    itemX, itemY = itemX * 2, itemY * 2
    answer = bfs(characterX * 2, characterY * 2, 0) // 2

    return answer