[프로그래머스] 아이텝 줍기 - 파이썬

 

---

복기

BFS로 풀어야하는 것은 쉽게 파악했다. 이 문제에서는 2가지만 챙겨가자.

1.

일반적인 2D 배열 (Top-Left 기준)

• arr[0][0] : 맨 위, 맨 왼쪽
• arr[y][x] : y가 증가하면 아래로 이동, x가 증가하면 오른쪽으로 이동
• 이때 '위로' 가려면 y-1을 해야 합니다.

2. 이 코드의 방식 (Bottom-Left 기준)

이 코드는 2D 배열을 마치 수학의 xy 좌표평면처럼 쓰고 있습니다.

• graph[x][y] : x좌표, y좌표
• x가 증가하면 오른쪽으로 이동 (graph[1][1] -> graph[2][1])
• y가 증가하면 위로 이동 (graph[1][1] -> graph[1][2])

-> 즉 2D 배열을 xy 좌표평면처럼 일관되게 세팅해서 풀면 훨씬 쉽다

 

---

문제가 되는 상황 (좌표 1배)

블록 2개가 딱 붙어있는 상황을 상상해 보세요.

• A = 캐릭터 위치 (3, 5)
• B = 아이템 위치 (3, 6)
• C = 붙어있는 다른 사각형의 모서리 (4, 5)
• D = 붙어있는 다른 사각형의 모서리 (4, 6)

  (3,6) B-------D (4,6)
        |       |
  (3,5) A-------C (4,5)

올바른 길 (테두리): A → C → D → B (총 3칸) BFS가 찾는 최단 길: A → B (총 1칸)

BFS는 A와 B가 바로 붙어있다고 생각해서, C와 D로 돌아가는 길 대신 벽을 뚫고 A에서 B로 바로 가는 길을 선택합니다.

---

2. 해결책 (좌표 2배)

이 문제를 해결하기 위해, 모든 좌표를 2배로 늘려 "선"이었던 길을 "면(도로)"으로 만들어 줍니다.

• A (3, 5) → A' (6, 10)
• B (3, 6) → B' (6, 12)
• C (4, 5) → C' (8, 10)
• D (4, 6) → D' (8, 12)

이제 그림이 이렇게 바뀝니다.

(6,12) B'--?--D' (8,12)
        |     |
(6,11)  ?-----?  (8,11)  <-- "새로 생긴 길"
        |     |
(6,10) A'-----C' (8,10)

핵심은 (6, 11)과 같은 "새로 생긴 길"입니다.

1. 길이 넓어짐: A'에서 C'로 가는 길은 (6,10) → (7,10) → (8,10)이 됩니다. "선"이 "도로"가 되었습니다.
2. 벽 생성: A'에서 B'로 가려고 보니, 중간에 (6, 11)이라는 새로운 좌표가 생겼습니다.
3. 최단 경로 차단: 이 (6, 11)은 다른 사각형의 테두리이거나 내부일 수 있습니다. 이 부분을 **'못 가는 길(벽)'**로 칠해버립니다. (링크의 코드에서 graph[i][j] = 0으로 처리하는 부분)
4. 우회: BFS는 A'(6,10)에서 B'(6,12)로 바로 가고 싶어도, (6,11)이 '벽'으로 막혀있어서 갈 수 없습니다.
5. 올바른 길 탐색: 결국 BFS는 '벽'이 아닌 길, 즉 테두리(도로)를 따라서 A' → C' → D' → B'로 가는 올바른 길을 찾게 됩니다. ((6,10) → ... → (8,10) → ... → (8,12) → ... → (6,12))

---

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    graph = [[-1 for _ in range(102)] for _ in range(102)]
    # 1. visited 배열을 -1 (방문 안 함)로 초기화
    visited = [[-1 for _ in range(102)] for _ in range(102)] 
    direction = [(0, -1), (1, 0), (0, 1), (-1, 0)]
    
    # ... (graph 그리는 부분은 동일) ...
    for r in rectangle:
        x1, y1, x2, y2 = map(lambda x: x*2, r)
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                if x1 < i < x2 and y1 < j < y2:
                    graph[i][j] = 0
                elif graph[i][j] != 0:
                    graph[i][j] = 1                
    
    cx, cy, ix, iy = 2*characterX, 2*characterY, 2*itemX, 2*itemY
    q = deque()
    q.append((cx, cy))
    
    # 2. 시작점 방문 처리 (거리는 0)
    visited[cx][cy] = 0 
    
    while q:
        x, y = q.popleft()
        
        if x == ix and y == iy:
            # 5. 최종 답 계산 (2배된 거리를 2로 나눔)
            answer = visited[x][y] // 2 
            break   
        
        for k in range(4):
            nx, ny = x + direction[k][0], y + direction[k][1]
            
            # 3. (길이 맞고) (아직 방문 안 했는지) 확인
            if graph[nx][ny] == 1 and visited[nx][ny] == -1: 
                
                # 4. 거리 갱신 (현재 거리 + 1) 및 큐에 추가
                visited[nx][ny] = visited[x][y] + 1 
                q.append((nx, ny))

    return answer