프로그래머스) 아이템 줍기 (lv.3)

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

프로그래머스

 

 

탐색을 이용하여 최단 경로를 찾는 DFS/BFS의 문제 유형이다. 겹치도록 제작된 사각형들의 바깥 테두리따라 시작 지점부터 최종지점까지 최단 경로를 구하는 문제이다. 

 

여기서 주의할 점은 칸이 아닌 테두리를 이용하여 경로를 이용하는 것으로 1개 간격으로 테두리 모양을 이룰 경우 이를 같은 칸으로 인식할 수 있기 때문에 보드의 크기와 모든 수를 2배로 하여 경로를 구한 뒤, 값을 구해야 한다는 점이다. 

 

보드에 사각형을 그릴 때, 사각형이 겹치지 않는 테두리 부분만 1로 잡아서 갈 수 있는 경로를 표시하고, 사각형 외부는 0, 사각형 내부는 -1로 표시되도록 하였다. 

 

BFS를 이용하여 시작지점에서 이동할 수 있는 공간(테두리이면서 방문하지 않은 공간)으로 이동하면서 보드의 값을 없데이트하여 최단경로의 길이를 구하도록 하였다. 

 

여기서 시작점은 1로 (테두리 기본값) 시작하였기 때문에 마지막 값을 구할 때 board[x][y]-1 을 해주었고, 모든 수를 2배로 해주었기 때문에 경로 값도 //2로 최종 값을 구하도록 했다. 

 

 

from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    board = [[0]*101 for _ in range(101)]
    visited = [[False]*101 for _ in range(101)]
    characterX *= 2
    characterY *= 2
    itemX *= 2
    itemY *= 2
    for rec in rectangle :
        left_x, left_y, right_x, right_y = map(lambda x : x*2, rec)
        for i in range(left_x, right_x + 1) :
            for j in range(left_y, right_y + 1):
                if left_x < i <right_x and left_y < j < right_y :
                    board[i][j] = -1
                elif board[i][j] != -1 :
                    board[i][j] = 1
    
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    q = deque()
    q.append((characterX, characterY))
    visited[characterX][characterY] = True
    
    while q :
        x, y = q.popleft()
        if (x, y) == (itemX, itemY):
            answer = (board[x][y] -1)//2
            break
        for direction in directions : 
            nx = x + direction[0]
            ny = y + direction[1]
            if 0<= nx <101 and 0<= ny < 101 and board[nx][ny] == 1 and not visited[nx][ny] : 
                board[nx][ny] = board[x][y] + 1
                visited[nx][ny] = True
                q.append((nx, ny))
    return answer