좌표 문제

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

아이템 줍기

from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
    data = rectangle
    MAX = 102 #최대 칸수 200으로 잡고
    g = [[-1] * MAX for _ in range(MAX)] #그래프
    
    #그래프 좌우 뒤집어도 동일 ! 행, 열 뒤집어도 된다는 뜻.
    
    for x1,y1,x2,y2 in data: #사각형 좌표
        for i in range(2*x1, 2*x2+1):  #좌표값 2배로 !!
            for j in range(2*y1, 2*y2 + 1):
                #x1,x2,y1,y2는 테두리 이므로 제외하고 내부만 0으로 채우기
                if x1*2 < i < x2*2 and y1*2 < j <y2*2:
                    g[i][j] = 0 #사각형 0로 채우기 (내부)
                elif g[i][j] != 0: #다른 직사각형의 내부가 아니면서 테두리일때 (테두리 중에도 다른 직사각형의 내부에 포함될 수도 있으니)
                    g[i][j] = 1
    
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    dis = [[0] * MAX for _ in range(MAX)] #최단거리
    def BFS(a,b):
        dq = deque()
        dq.append((a,b))
        g[a][b] = 0  #시작점 방문 표시. (테두리 -> 내부 표시로 바꿈)
        
        while dq:
            x,y = dq.popleft() #현재 좌표 가져와서
            if x == itemX * 2 and y == itemY * 2:
                res = dis[x][y] // 2
                return res
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                # if g[nx][ny] == 1 and dis[nx][ny] == 0: #아직 방문 전이면서 테두리이면 갈 수 있고, 갱신!
                #     dis[nx][ny] = dis[x][y] + 1
                #     dq.append((nx,ny))
                if 0<=nx<MAX and 0<=ny<MAX:
                    if g[nx][ny] == 1: #아직 방문 안한 좌표. 
                        g[nx][ny] = 0
                        dis[nx][ny] = dis[x][y] + 1
                        dq.append((nx,ny))
    res = BFS(characterX * 2, characterY * 2)   #맵을 애초에 2배로 키웠기 때문에, 시작 좌표 도착 좌표 모두 2배로 키워줘야 한다.
    # print(res)
    return res

    # 좌표를 좀더 넉넉하게 주어도 되겠다.
    
                
    

🎈 코멘트

해당 문제는 우선 테두리를 포함한 사각형(테두리 + 내부)을 1로 채운다.
그리고 사각형 테두리를 0으로 채워 가장 바깥쪽 테두리만 남긴다.
마지막으로 탐색을 통해 캐릭터와 아이템 사이의 최단 경로를 구한다.

1. 좌표를 2배로 확대

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

이럴 경우를 대비해서 좌표를 그릴 때 2를 곱해서 그려주고, 구한 최단거리를 다시 2로 나눠주면 된다.

2. 너비우선 탐색

캐릭터의 위치를 상하좌우로 움직이며 아이템까지의 최단 거리를 구한다.
이미 탐색한 좌표에 대해서 방문 처리 잊으면 안된다.