프로그래머스_아이템 줍기

문제

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

코딩테스트 연습 - 아이템 줍기

풀이

우선, (1) 테두리를 포함한 사각형을 1로 채운다.

그리고 (2) 사각형의 내부를 0으로 채워 가장 바깥쪽 테두리만 남긴다.

마지막으로 (3) 탐색을 통해 캐릭터와 아이템 사이의 최단 경로를 구한다.

1. 좌표를 2배로 확대

주어진 좌표에 따라 사각형을 그려보면, 좌표가 인접한 경우 탐색을 제대로 하기 어렵다. 따라서, 좌표를 2배로 확대해서, 테두리 사이의 공간을 마련해 주어야 한다.

2. 너비우선탐색

캐릭터의 위치를 상하좌우로 움직여가면서 아이템까지의 최단 거리를 구한다.

아래 코드에서는 이미 탐색한 좌표에 대해서는 -1을 저장하여 다시 방문하지 않도록 했다.

코드

def solution(rectangle, characterX, characterY, itemX, itemY):
    MAXNUM = 1000
    board = [[0 for j in range(MAXNUM)] for i in range(MAXNUM)]
    
    # 사각형 1로 채우기 (테두리+내부)
    for c1, r1, c2, r2 in rectangle : 
        for i in range(2*r1, 2*r2+1) :
            for j in range(2*c1, 2*c2+1) : 
                board[i][j] = 1
    
    # 사각형 테두리 0으로 채우기 
    for c1, r1, c2, r2 in rectangle :             
        for i in range(2*r1+1, 2*r2) : 
            for j in range(2*c1+1, 2*c2) :  
                board[i][j] = 0
    
    # 테두리 따라가기
    chR, chC, itR, itC = 2*characterY, 2*characterX, 2*itemY, 2*itemX
    stack = [(0, chR, chC)]
    while stack : 
        w, chR, chC = stack.pop(0) # 너비 우선 탐색
        board[chR][chC] = -1 # passed
        
        if board[itR][itC]<0 : return w//2
        
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)] : 
            if board[chR+dr][chC+dc]>0 : 
                stack.append((w+1, chR+dr, chC+dc))