[프로그래머스/Python] - Lv3 / 아이템 줍기

아이템 줍기

level3-BFS(최단경로)-아이템 줍기

from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
    data = rectangle
    MAX = 200
    g = [[-1] * MAX for _ in range(MAX)]
    
    for x1,y1,x2,y2 in data:
        for i in range(x1*2, x2*2 + 1):
            for j in range(y1*2, y2*2 + 1):
                if x1*2 < i < x2*2 and y1*2 <j< y2*2:
                    g[i][j] = 0
                elif g[i][j] != 0: #다른 직사각형의 내부가 아니면서 테두리.
                    #테두리더라도 다른 직사각형의 내부라면 안돼!
                    g[i][j] = 1 #움직일 수 있는 테두리
    #맵은 다 만듬. 이제 최단거리
    dis = [[0] * MAX for _ in range(MAX)]
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    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:
                return dis[x][y] // 2 #최단거리 역시 //2 해줘야함 !!
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                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))
        
        
    
    #시작점 도착점 모두 맵을 2배씩 키워야 한다 !!
    res = BFS(characterX * 2, characterY * 2)
    print(res)   
    return res

😀 코멘트

해당 문제는 사각형의 좌표가 주어지고 테두리를 따라서 최단경로를 찾는 문제이다.
이런 유형의 문제를 만났을 때 당황하면 안된다. 결국 큰 틀은 BFS를 이용한 최단거리인데, 주어진 그래프(맵)가 없는 것이다.

• 그 뜻은 내가 직접 맵을 만들면 된다는 뜻 !!

문제 해결 아이디어

사각형이 그려진 좌표를 만들기

• 2차원 배열을 만들어서 사각형 내부, 외부에 따라 값을 따로 준다. 테두리만이 움직일 수 있는 좌표가 되도록 설정 !

2차원 배열을 만들 때 한번 더 생각해야 하는 부분이 있는게 그게 바로 테두리가 인접했을 경우이다.

위와 같은 경우를 대비해서 좌표를 그릴 때 2를 곱해서 그려주고, 구한 최단거리 역시 2를 나눠주어야만 한다.

ref.참고한 블로그