[programmers] 87694. 아이템 줍기 (추천!)

문제

87694. 아이템 줍기

My thought

• 항상 그렇듯, BFS/DFS는 초기에 그래프를 얼마나 "잘" 구성하냐가 중요한 것같다 !_!
  재밌는 문제이고 풀어볼 만한 문제인 것 같다!

분석

• 직사각형의 가장 바깥쪽 테두리만 이동경로(그래프의 vertex들)가 될 수 있다.
  $\rightarrow$ 이를 통해 map을 나눌 때 경계선이 테두리가 된다.
  테두리를 기준으로 나누어보면 다음과 같고 다음의 기준으로 map을 만들어야한다.

1. 테두리 $\rightarrow$ 1 로 표현
2. 직사각형 안쪽 $\rightarrow$ 0 로 표현
3. 직사각형 바깥쪽 $\rightarrow$ -1 로 표현

• 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 해야한다.
  $\rightarrow$ BFS 풀 시에는 시간초과가 날 수 있으므로 조심!

내 코드에서 유의할 점

• 문제에서는 정점의 idx 1부터 시작하도록 하여, 나는 처음 모든 idx에 -1 연산을 해주고 풀었다. ((0,0)부터 idx를 시작하기 위해)

시행착오

• 인덱스를 그대로 사용하여 map을 만들면, 올바른 테두리를 따라서 가지 않고, 직사각형의 내부로 지나갈 수 있다. 이를 유념하면, map의 모든 idx를 2배해주어 풀어야한다!
  이에 대한 설명은 해당 블로그에 굉장히 잘 정리되어 있어서 링크 남겨둔다!!

코드 - BFS

from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):

    rect_n = len(rectangle)
    rect_map = [[-1]*100 for i in range(100)]
    visited = [[0]*100 for i in range(100)] # 초기화: 0
    queue = deque()
    
    ############ 1. 모든 정점의 idx에 2 * (idx - 1) ############ 
    characterX, characterY = 2*(characterX-1), 2*(characterY-1)
    itemX, itemY = 2*(itemX-1), 2*(itemY-1)
    ############################################################
    
    ############ 2. Map(Graph)을 만들어보쟈~! ############ 
    for n in range(rect_n):
        x1, y1, x2, y2 = map(lambda x: (x-1)*2, rectangle[n])
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                # 직사각형 내부
                if (x1<i and i<x2) and (y1<j and j<y2):
                    rect_map[i][j] = 0
                # 직사각형 모서리
                elif rect_map[i][j] != 0: 
                    rect_map[i][j] = 1
    #####################################################
    
    dir = [(0,1), (-1,0), (0,-1), (1,0)]
    
    visited[characterX][characterY] = 1     # visited
    queue.append((characterX, characterY, 0))
    
    min_result = 0
    
	############ 3. BFS 시작! ############ 
    while queue:
        cur_x, cur_y, depth = queue.popleft()
        #print(cur_x, cur_y, depth)
        
        # 끝낼 조건
        if cur_x == itemX and cur_y==itemY:
            min_result = depth//2
            #print(cur_x, cur_y, depth)
            break
        
        for dx, dy in dir:
            next_x, next_y = cur_x+dx, cur_y+dy
            #print("next: ", next_x, next_y)
            if 0<=next_x<100 and 0<=next_y<100:
                if not visited[next_x][next_y] and rect_map[next_x][next_y]==1:
                    visited[next_x][next_y]=1 # 방문처리
                    queue.append((next_x, next_y, depth+1))
                
    return min_result