Level 3

문제

해당 문제 링크

정답

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    MAX = 102 # 두배로 늘리기 때문에 최대 102 (51*2)
    
    #테두리 그리기
    field = [[5] * MAX for _ in range(MAX)] #5는 맨처음 땅
    for rec in rectangle :
        x1, y1, x2, y2 = map(lambda x : x*2, rec) #각각 모든 좌표갑에도 2배씩 늘림
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                #x1, x2, y1, y2는 테두리이므로 제외하고 내부만 0으로 채움
                if x1<i<x2 and y1<j<y2: # 내부일 때
                    field[i][j] =0
                # 다른 직사각형의 내부가 아니면서 테두리일 때 1로 채움
                elif field[i][j] !=0: # 테두리일때 그리고 이미 내부가 아닐 때
                    field[i][j]=1 # 테두리랑 내부랑 겹치면 그건 내부
    
    # 길 찾기 (최단 거리는 BFS)
    q=deque()
    q.append([characterX *2, characterY *2]) #캐릭터 출발 지점 추가
    visited=[[0] * MAX for _ in range(MAX)] # 방문 체크 2차원 배열 초기화
    visited[characterX * 2][characterY * 2]=1 #방문 체크
    
    dx=[1, -1, 0, 0]
    dy=[0, 0, 1, -1]
    
    while q:
        x, y = q.popleft()
        if x ==itemX *2 and y == itemY * 2: #아이템 있는 곳 도착하면
            answer = (visited[x][y] -1) // 2 # *2해줬던 것을 다시 2로 나눠줌
            break
            
        # 상하좌우 네 방향을 체크하면서    
        for k in range(4):
            nx = x+dx[k]
            ny = y+dy[k]
            # 현재 좌표가 테두리이고 아직 방문하지 않은 곳이라면 q에 추가 후 visited 최단거리로 갱신
            if visited[nx][ny] ==0 and field[nx][ny] ==1:
                q.append([nx, ny])
                visited[nx][ny] = visited[x][y] +1
                        
    return answer

풀이

아래와 같은 구조로 만들어진다.
1인 테두리만 따라가서 최단거리를 구한다.

주어진 좌표에서 그대로 하게 되면
1칸 차이밖에 안난다면, 테두리가 겹치게 된다.
그리하여 전체 좌표에 2배를 주고 테두리를 잡았다
아이템을 주웠다면 그때 //2로 나누기를 하여 돌아온다!

각 줄에 대해 자세한 설명은 주석을 통해 작성했다.

코드 및 그림 참고 사이트