[Programmers] 아이템 줍기

[Programmers] 아이템 줍기

Question

Language: Python

우선 가장 바깥쪽 둘레에 대한 그래프를 그린후, 출발지점으로 부터 bfs를 이용해서 목적지까지의 최단 거리를 구하면 된다. 이때, y좌표 값들은 배열의 구조를 생각해서 뒤집어준다.

그래프를 그릴때는, 테두리 부분에 속한 좌표들은 1로 초기화하고, 내부에 있는 값은 0으로 초기화해서 접근하지 못하도록한다. 그리고 이미 한번 초기화 된 그래프값에 대해서는 초기화가 이루어지지 못하도록 조건문을 설정한다(겹치면서 0이었던 값이 1이 될수도 있는 경우 발생)

, 예제 1번을 보면 가장 바깥쪽 둘레를 구하면 오른쪽 그림과 같다. 하지만, 이대로 bfs를 진행하게 되면 문제가 발생하게 되는데, [3,5] 지점에서 경로를 판단해보면 원래대로면 [4,5] 밖에 길이 존재하지 않지만, 실제로는 [3,6] 으로의 길도 bfs을 통해 갈 수 있다고 판단될 수 없다. 이렇게 되는 원인은 길이가 1인 간선들로 이루어져 있어서 생기는 문제로, 전체적으로 모든 좌표값을 2배씩 scaling 해서 bfs을 수행하고 나중에 거리값에서 절반으로 나눈다.

이 문제의 핵심은 2배 scaling하는 것이다.

Solution

from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]
    graph=[[-1] *(101) for _ in range(101)]
    
    
    #2배로 scaling
    for i in range(len(rectangle)):
        rectangle[i]=list(map(lambda x: x*2,rectangle[i]))
    
    characterX*=2
    characterY*=2
    itemX*=2
    itemY*=2
    

    for start_x, start_y,end_x,end_y in rectangle:
        for i in range(start_x,end_x+1):
            for j in range(100-end_y,100-start_y+1):
                #초기화 되지 않은 좌표들만 초기화한다.
                if graph[j][i]==-1:
                    #테두리에 있는 경우
                    if i==start_x or i==end_x or j==100-start_y or j==100-end_y:
                        graph[j][i]=1
                    #내부에 있는 경우
                    else:
                        graph[j][i]=0
                #만약 1로 초기화 되었다 하더라도 해당 좌표가 다른 직사각형의 내부에 속하게 되면 이를 0으로 초기화시켜줘야한다.
                elif graph[j][i]==1:
                    if i!=start_x and i!=end_x and j!=100-start_y and j!=100-end_y:
                        graph[j][i]=0
                        
    #거리를 저장하는 visited 배열
    visited=[[0]*101 for _ in range(101)]
    queue=deque([(100-characterY,characterX)])
    visited[100-characterY][characterX]=0
    
    while queue:
        row,col=queue.popleft()
        
        if row==100-itemY and col==itemX:
            #2배 scaling 한것을 원복 시킨다.
            answer=visited[row][col]//2
            break
        
        for dir in range(4):
            new_row=row+dy[dir]
            new_col=col+dx[dir]
            
            if new_row < 0 or new_row >100 or  new_col < 0 or new_col >100:
                continue
            if graph[new_row][new_col]==1:
                if visited[new_row][new_col]==0:
                    visited[new_row][new_col]=visited[row][col]+1
                    queue.append((new_row,new_col))


    return answer