TIL 07-14 보급로

김덕협·2026년 7월 14일

TIL

목록 보기

31/41

문제 정보

문제 이름: [S/W 문제해결 응용] 4일차 - 보급로 (1249번)
문제 링크: SWEA 1249. 보급로
알고리즘 분류: 그래프 이론, 다익스트라 (Dijkstra), 최단 경로

풀이 과정

1 문제 분석 및 제약 조건 확인

문제 분석

출발지 $(0, 0)$ 에서 도착지 $(N-1, N-1)$ 까지 이동할 때, 지도의 각 칸에 적힌 파여진 깊이(복구 시간)의 합을 최소화하는 경로를 찾는 문제다.
이동은 상, 하, 좌, 우 4방향으로만 가능하다.
단순한 최단 거리(이동 횟수 최소)가 아닌, 각 칸을 지날 때 발생하는 비용(가중치)의 합을 최소화해야 하는 전형적인 최소 비용(최단 경로) 문제다.

제약 조건

지도의 크기 $N$ 은 최대 $100 \times 100$ 이다.
각 칸의 파여진 깊이(시간)는 $0$ 에서 $9$ 사이의 정수다.
그래프의 모든 가중치가 $0$ 이상(양수 가중치)이므로, 다익스트라(Dijkstra) 알고리즘을 적용하기에 매우 적합하다.

2 알고리즘 및 자료구조 선택

다익스트라 알고리즘 (Dijkstra Algorithm)

BFS는 모든 간선의 가중치가 동일할 때 최단 거리를 보장하지만, 이 문제처럼 칸마다 이동 비용(가중치)이 다를 때는 최단 경로를 보장하지 못한다.
따라서, 우선순위 큐(Priority Queue)를 사용하는 다익스트라 알고리즘을 선택했다.
가중치가 가장 낮은 노드부터 차례대로 방문하기 위해 파이썬의 최소 힙(heapq) 자료구조를 활용한다.

자료구조 설정

grid (2차원 리스트): 입력받은 지도의 가중치 정보 저장
dist (2차원 리스트): 출발지로부터 각 위치 $(y, x)$ 까지 도달하는 최소 비용을 기록. 초기값은 무한대(float('inf'))로 설정한다.
pq (우선순위 큐): 누적 비용이 가장 낮은 경로를 먼저 꺼내기 위해 (누적 비용, y, x) 형태의 튜플을 담는 최소 힙으로 구현한다.

3 절차적 구현 흐름

작성한 코드의 다익스트라 함수는 다음과 같은 흐름으로 작동한다.

초기화
- 출발점의 최소 비용을 지도 시작 지점의 가중치로 설정한다: dist[0][0] = grid[0][0]
- 우선순위 큐 pq에 초기 상태인 (grid[0][0], 0, 0)을 삽입한다.
루프 및 유효성 검사
- 큐가 빌 때까지 반복하며, 가장 누적 비용이 적은 노드 (curr_dist, sy, sx)를 꺼낸다 (heapq.heappop).
- 만약 꺼낸 curr_dist가 이미 기록된 최소 비용인 dist[sy][sx]보다 크다면, 이는 이미 더 짧은 경로가 발견된 것이므로 무시하고 넘어간다 (continue).
- 만약 목적지인 (N-1, N-1)에 도달했다면 가중치가 최소인 경로를 찾은 것이므로 즉시 탐색을 종료하고 반환한다.
인접 노드 탐색 및 완화(Relaxation)
- 현재 위치 (sy, sx)에서 상, 하, 좌, 우 4방향으로 이동할 다음 위치 (ny, nx)를 계산한다.
- 지도 범위 내부(0 <= ny < N 및 0 <= nx < N)인 경우, 다음 칸까지의 예상 비용을 계산한다:
  next_dist = curr_dist + grid[ny][nx]
- 만약 계산한 next_dist가 기존에 기록되어 있던 최소 비용 dist[ny][nx]보다 작다면:
  - 값을 next_dist로 갱신(완화)한다.
  - 갱신된 정보를 우선순위 큐에 다시 넣어 다음 탐색의 후보로 만든다: heapq.heappush(pq, (next_dist, ny, nx))

4 시간 복잡도

정점(Vertex)의 수 $V$ : 지도의 전체 칸 수인 $N \times N = N^2$ 이다.
간선(Edge)의 수 $E$ : 각 칸에서 상하좌우 4방향으로 이동할 수 있으므로 약 $4 \times N^2$ 이다. ( $E \approx 4N^2$ )
다익스트라 시간 복잡도: $O(E \log V)$
- 우선순위 큐를 사용하는 다익스트라 알고리즘의 시간 복잡도는 $O(E \log V)$ 이다.
- 이를 이 문제에 대입하면 $O(4N^2 \log(N^2)) = O(N^2 \log N)$ 이 된다.
- $N = 100$ 일 때, $N^2 = 10,000$ 이고 $\log_2(100) \approx 6.64$ 이므로 연산 횟수는 약 수십만 번 이내로 파이썬 제한 시간 내에 매우 안정적으로 통과할 수 있다.

5 전체 소스코드

import heapq

# 상 우 하 좌
dx = [0, 1, 0, -1]
dy = [-1, 0 ,1, 0]

def dijkstra():
    dist[0][0] = grid[0][0]
    
    # (누적 비용, y, x)
    pq = [(grid[0][0], 0, 0)]
    
    while pq:
        curr_dist, sy, sx = heapq.heappop(pq)
        
        # 최적화: 이미 방문하여 더 작은 값으로 갱신되었다면 스킵
        if curr_dist > dist[sy][sx]:
            continue
        
        # 도착점에 도달했다면 종료
        if sy == N-1 and sx == N-1:
            return
        
        for i in range(4):
            ny, nx = sy + dy[i], sx + dx[i]
            
            if 0 <= ny < N and 0 <= nx < N:
                next_dist = curr_dist + grid[ny][nx]
                
                # 가중치 완화 조건 조건
                if next_dist < dist[ny][nx]:
                    dist[ny][nx] = next_dist
                    heapq.heappush(pq, (next_dist, ny, nx))
                
                    
T = int(input())

for tc in range(1, T+1):
    N = int(input())
    grid = [list(map(int, input())) for _ in range(N)]
    dist = [[float('inf')] * N for _ in range(N)]
    
    dijkstra()
    print(f"#{tc} {dist[N-1][N-1]}")