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

문제

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

내 코드

from collections import deque
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def isInner(x,y):
    if 0<=x<102 and 0<=y<102:
        return True
    return False

def solution(rectangle, characterX, characterY, itemX, itemY):
    # 아이템 줍기
    # 다각형 모양 지형에서 캐릭터가 아이템 줍기 위해 이동해야 한다.
    # 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현, 캐릭터는 둘레를 따라서 이동
    # 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리 구하기 
    # 초기 캐릭터 위치 (cX,cY)
    # 아이템 위치 (itemX,itemY)
    # rectangle은 (좌하단좌표, 우상단좌표)가 주어진다.
    
    # 좌표 확장을 통해 애매한 경계선 처리 해결 가능
    
    # 좌표 확장(2배)
    g = [[0] * 102 for _ in range(102)]
    # 직사각형 테두리 표시
    for x1,y1,x2,y2 in rectangle: # 좌하단 좌표, 우상단 좌표
        x1,y1,x2,y2 = x1*2,y1*2,x2*2,y2*2 # 좌표 확장  -> 이 부분에서 시작 부분도 확장해줬어야 함
        for i in range(x1, x2 + 1):
            for j in range(y1, y2 + 1):
                if x1 < i < x2 and y1 < j < y2: # 내부
                    g[i][j] = 2 # 내부 처리
                elif g[i][j] != 2:
                    g[i][j] = 1 # 테두리 처리
    

    def BFS(startX,startY):
        dq = deque()
        dq.append((startX,startY,0))
        INF = int(1e9)
        dis = [[INF] * 102 for _ in range(102)]
        dis[startX][startY] = 0
        
        while dq:
            x,y,d = dq.popleft() # 현재 위치, 현재까지의 최단거리
            if (x,y) == (itemX*2,itemY*2):
                return d // 2
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if not isInner(nx,ny): continue
                if g[nx][ny] == 1: # 테두리
                    if d + 1 < dis[nx][ny]:
                        dis[nx][ny] = d + 1
                        dq.append((nx,ny,d+1))
    res = BFS(characterX * 2,characterY * 2)
    print(res)
    return res

코멘트

직사각형들이 겹쳐진 도형의 테두리를 따라 이동해야 한다.
-> 캐릭터는 항상 테두리만 따라서 이동할 수 있다.
시작점에서 도착점까지의 최단거리 구하기

주요 난점
1. 겹치는 직사각형들로 인해서 단순한 2D 그리디로는 문제를 해결할 수 없다.
2. 테두리만 따라 이동해야 하므로, 내부로 이동하는 경우 제외해야 한다.

접근 방법
1. 좌표 확장

• 모든 좌표를 2배 확장한다. (1,1) -> (2,2)
• 이렇게 하면 겹치는 부분을 정확히 표현할 수 있다.
• 확장 전에 붙어있는 두 직사각형의 경계가 하나의 선으로 표현되어 최단거리를 구하는데 있어서 힘들었는데 해결 가능.

2. 테두리 표시

• 확장된 좌표계에서 각 직사각형의 테두리를 1로 표시한다.
• 내부는 0으로 남겨둔다.

좌표를 2배 확장하는 것의 의미

(1,1) --- (3,1)
  |         |
  |         |
(1,3) --- (3,3)

위 경우에서 이제 좌표를 2배 확장하게 되면

(2,2) ----- (6,2)
  |           |
  |           |
  |           |
  |           |
(2,6) ----- (6,6)

이 경우가 된다. 이렇게 확장하면 몇 가지 중요한 변화가 생기는데,

1. 더 세밀한 그리드

• 원래 좌표 사이에 새로운 격자점들이 생긴다.
• 예 (1,1)과 (2,1) 사이에 (3,2)라는 새로운 점이 생긴다.

2. 대각선 이동 방지

• 원래 좌표계에서 (1,1)에서 (2,2)로 대각선 이동이 가능했다면, 화장된 좌표계에서는 (2,2)에서 (4,4)로 가려면 반드시 (2,4)나 (4,2)를 거쳐가야 한다.

3. 테두리 명확화

• 원래 좌표계에서는 두 직사각형이 붙어있을 때 구분이 어려웠지만, 확장된 좌표계에서는 테두리 사이에 빈 공간이 생겨 명확히 구분된다.

4. 내부와 외부 구분

• 확장된 좌표계에서는 직사각형의 내부와 테두리를 더 쉽게 구분할 수 있다.

실제 구현에서

• 입력된 모든 좌표값에 2배를 곱한다. (x,y) -> (2x,2y)
• 그리드의 크기도 2배 늘린다. (50x50) -> (100,100)
• BFS등의 알고리즘을 적용할 때 이 확장된 그리드를 사용하면 된다.
• 최종 결과를 얻을 때 거리 2로 나누면 원래 스케일이 가능

직사각형 테두리 표시할 때 주의점

1. 내부와 테두리 구분

• 2는 직사각형의 내부
• 1은 직사각형의 테두리를 나타낸다

2. 겹치는 직사각형 처리

• 여러 직사각형이 겹칠 때, 한 직사각형의 테두리가 다른 직사각형의 내부에 위치할 수 있다. 이 경우 테두리로 표시되어야 할 부분이 내부로 잘못 표시되는 것을 방지한다.

3. 우선순위

• 내부(2)가 테두리(1)보다 우선순위가 높다. 한번 내부로 표시된 칸은 다시 테두리로 바뀌면 안된다.

4. 정확성 보장

• 이 방식을 통해 겹치는 직사각형들의 복잡한 구조에서도 정확한 테두리를 표시할 수 있다.

예를 들어,

+-----+
   |     |
+--|--+  |
|  |  |  |
|  +--|--+
|     |
+-----+

이 경우, 겹치는 부분의 일부는 한 직사각형의 테두리이면서 다른 직사각형의 내부.
테두리 처리 코드는 아래와 같이 작동한다.

1. 첫번째 직사각형을 처리할 때, 모든 테두리를 1로 표시한다.
2. 두번쨰 직사각형 처리할 때

• 내부는 2로 표시
• 테두리 중 이미 2로 표시된 부분 (다른 직사각형의 내부)은 그대로 2로 남는다.
• 나머지 테두리는 1로 표시된다.

백준-2636 치즈 문제 풀어보자.