[프로그래머스] 아이템 줍기 (BFS) - Python

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

프로그래머스

 

아이디어 

1. 사각형 테두리를 그린다. 

2. 테두리 따라서 , characterX, characterY 좌표부터 itemX, itemY 까지의 경로중 최단거리를 BFS를 이용해서 탐색한다 

여기서 주의해야 할 점은, 테두리와 테두리가 겹치는 경우 경로를 잘못 인식할 수 있다는 점이다. 따라서, 아예 2배로 칸 크기를 늘려서, 겹치는 문제를 해결해야 한다. 대신 answer 를 구할 때 다시 2로 나누어주면 된다. 

 

from collections import deque 

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

    

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    
    board = [[-1] * 102 for _ in range(102)]
    visited = [[0] * 102 for _ in range(102)]
    for rec in rectangle:
        x1, y1, x2, y2 = map(lambda x: x*2, rec)
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                if x1 < i < x2 and y1 < j < y2:
                    board[i][j] = 0
                elif board[i][j] != 0: # 이미 직사각형 안이 아니면서, 테두리로 그릴 수 있는 경우 -> 직사각형끼리 겹치는 경우 방지 
                    board[i][j] = 1 # 테두리 그리기 
    
    # for i in range(50):
    #     print(board[i])
    
    def bfs():
        queue = deque()
        queue.append([characterX*2, characterY*2]) # start 
        visited[characterX*2][characterY*2] = 1 # 방문 표시
        while queue:
            x, y = queue.popleft() 
            if x == itemX * 2 and y == itemY * 2:
                answer = (visited[x][y] -1) // 2
                return answer 
                break 
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if board[nx][ny] == 1 and visited[nx][ny] == 0: # 테두리인 경우에만 이동 가능 
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append([nx, ny])
    
    answer = bfs()

    return answer