[프로그래머스] Lv.3 아이템 줍기 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/87694
• 겹치는 사각형들의 테두리만 잘 표현하면 BFS 구현만으로 풀 수 있다.
• 키 포인트 : 사각형의 크기를 2배로 늘린다.
• 사각형들의 크기를 2배로 키우는 이유는 꺾이는 부분에서 문제가 생기기 때문이다.

 

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    map = [[0] * 102 for _ in range(102)] # 사각형을 2배 크기로 그리기 위해 2배정도 늘린 맵
    visit = [[0] * 102 for _ in range(102)] # 방문 체크, 거리 체크

    for i in rectangle: # 사각형 그리기
        for j in range(i[1]*2, i[3]*2+1):
            for k in range(i[0]*2, i[2]*2+1):
                if map[j][k] == 4: # 이미 만들어진 사각형 안이면 건너뛰기
                    continue 
                if j == i[1]*2 or j == i[3]*2 or k == i[0]*2 or k == i[2]*2: # 테두리 부분은 1
                    map[j][k] = 1
                else:
                    map[j][k] = 4   # 테두리가 아니고 사각형 안이면 4

    que = deque([(characterY*2, characterX*2)]) # 시작 위치, 사각형이 2배라서 위치도 2배
    visit[characterY*2][characterX*2] = 1 # 시작 위치 1로 체크
    mx, my = [-1, 1, 0, 0], [0, 0, -1, 1] # 상,하,좌,우

    while que:
        x, y = que.popleft() # 현재 위치 x = 행, y = 열
        if x == itemY*2 and y == itemX*2: # 현재 위치가 아이템 위치면 리턴
             return visit[x][y] // 2 # 정답 리턴
        for i in range(4): # 상,하,좌,우 이동
            nx, ny = x + mx[i], y + my[i] # 다음 이동 위치 nx, ny
            if 0 <= nx <= 102 and 0 <= ny <= 102: # 맵 범위를 벗어나지 않을 때
                if map[nx][ny] == 1 and visit[nx][ny] == 0: # 테두리고 방문 안했을 때
                    que.append((nx, ny))
                    visit[nx][ny] = visit[x][y] + 1