[프로그래머스] 아이템 줍기

문제

• 다각형 모양의 둘레를 따라 캐릭터가 이동할 때, 특정 위치의 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리 찾기

• 캐릭터의 위치 (cX, cY)와 아이템의 위치 (iX, iY)가 주어진다.
• 1 <= 직사각형 개수 <= 4
• 1 <= X, Y <= 50

 

풀이

• 캐릭터가 움직일 수 있는 테두리선을 찾아야 한다.
  • 가로선으로 움직이는 경우와 세로선으로 움직이는 경우를 나눠서 표현한다.
  • 예를 들어 (1, 3) -> (1, 4) 는 (1, (3, 4)) 로 표현한다.
  • 직사각형의 테두리선을 추가하고, 직사각형 내부 선은 제거한다.
• 캐릭터의 위치에서 상하좌우로 움직일 때의 최단거리 찾기 (BFS)
  • 테두리선을 따라 움직이기 때문에 가능한 방향은 항상 2개가 존재한다.
  • 따라서 방문 배열을 하나만 두고, 이미 움직인 곳인지 확인하도록 한다.

 

from collections import deque

answer = 1e9
def solution(rectangle, characterX, characterY, itemX, itemY):
    maps = set()
    # 직사각형 테두리선 추가하기
    for lx, ly, rx, ry in rectangle:
        for x in range(lx, rx):
            maps.add(((x, x+1), ly))
            maps.add(((x, x+1), ry))
                
        for y in range(ly, ry):
            maps.add((lx, (y, y+1)))
            maps.add((rx, (y, y+1)))
    
    # 직사각형 내부 선 제거하기 (겹치는 부분들)
    for lx, ly, rx, ry in rectangle:
        for x in range(lx+1, rx):
            for y in range(ly, ry):
                if (x, (y, y+1)) in maps :
                    maps.remove((x, (y, y+1)))
        for y in range(ly+1, ry):
            for x in range(lx, rx):
                if ((x, x+1), y) in maps :
                    maps.remove(((x, x+1), y))
    
    # 최단거리 찾기
    visited = dict(zip(maps, [False]*len(maps)))    # 방문 배열
    q = deque([(characterX, characterY, 0)])
    
    while q:
        x, y, cnt = q.popleft()

        if x == itemX and y == itemY :  # 아이템에 도달한 경우
            return cnt
        
        if ((x-1, x), y) in maps and not visited[((x-1, x), y)]:   # 좌
            q.append((x-1, y, cnt+1))
            visited[((x-1, x), y)] = True
        if ((x, x+1), y) in maps and not visited[((x, x+1), y)]:   # 우
            q.append((x+1, y, cnt+1))
            visited[((x, x+1), y)] = True
        if (x, (y, y+1)) in maps and not visited[(x, (y, y+1))]:   # 위
            q.append((x, y+1, cnt+1))
            visited[(x, (y, y+1))] = True
        if (x, (y-1, y)) in maps and not visited[(x, (y-1, y))]:   # 아래
            q.append((x, y-1, cnt+1))
            visited[(x, (y-1, y))] = True
                
    return answer

 

 

 

References

• 프로그래머스 고득점Kit 아이템 줍기