[프로그래머스] 11주차_아이템 줍기

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

코딩테스트 연습 - 11주차

 

1) 테두리 좌표 기억하기

2) BFS 알고리즘 사용

으로 접근하였다.

 

테두리 좌표는 직사각형의 테두리와 내부를 board[][] = 1로 만든 다음, 내부를 board[][] = 0으로 바꿔준다.

어떤 직사각형에서 테두리가 다른 직사각형의 내부라면 board[][] = 0 으로 처리해줘야 하기 때문이다.

이때, 모든 좌표는 * 2 해준다. 입출력 예 1번 [3, 5] -> [4, 5] -> [4, 6] -> [3, 6] -> [2, 6] 에서 [3, 5] -> [3, 6] 사이에 [4, 5] -> [4, 6] 경로를 지나는 것을 계산하기가 어렵기 때문이다. 계산이 쉽게 2배씩 늘려 계산한다. 

 

다음, BFS 알고리즘을 이용하여 테두리의 (x, y) 로 가게 위한 최단 거리를 board[x][y] 에 기억하여 1씩 더하면서 최종적으로 아이템을 줍기까지의 최단 거리를 구한다.

모양을 2배 늘렸으므로 최종적인 답은 2를 나눠준다. (1을 빼는 이유는 board[cX][cY] = 1 로 시작했기 때문이다.) 

 

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    board = [[0] * 101 for i in range(101)]
    cX = 2 * characterX
    cY = 2 * characterY
    iX = 2 * itemX
    iY = 2 * itemY
    d = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    visited = [[0] * 101 for i in range(101)]
    visited[cX][cY] = 1
    queue = deque([(cX, cY)])
    
    for x1, y1, x2, y2 in rectangle:
        for i in range(2*x1, 2*x2+1):
            for j in range(2*y1, 2*y2+1):
                board[i][j] = 1
    
    for x1, y1, x2, y2 in rectangle:
        for i in range(2*x1+1, 2*x2):
            for j in range(2*y1+1, 2*y2):
                board[i][j] = 0
    
    while queue:
        x, y = queue.popleft()
        
        if (x, y) == (iX, iY):
            answer = (board[x][y] - 1) // 2
            break
        
        for i, j in d:
            xTemp = x + i
            yTemp = y + j
            
            if 0 <= xTemp < 101 and 0 <= yTemp < 101 and board[xTemp][yTemp] != 0 and visited[xTemp][yTemp] == 0:
                board[xTemp][yTemp] = board[x][y] + 1
                visited[xTemp][yTemp] = 1
                queue.append((xTemp, yTemp))
        
    return answer

print(solution([[1, 1, 7, 4], [3, 2, 5, 5], [4, 3, 6, 9], [2, 6, 8, 8]], 1, 3, 7, 8)) # 17