Graph: 백준 1753 오답노트

SeongGyun Hong·2025년 3월 8일
Graphpython데이크스트라최단 경로

Python

목록 보기
32/34

https://www.acmicpc.net/problem/1753

1. 문제 개요

  • 방향 그래프가 주어지며, 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제
  • 모든 간선의 가중치는 10 이하의 자연수

입력 형식:

  • 첫 줄: 정점 개수 ( V )와 간선 개수 ( E )
  • 둘째 줄: 시작 정점 ( K )
  • 이후 ( E )개의 줄: 각 간선을 나타내는 세 개의 정수 ( u, v, w )
    → ( u )에서 ( v )로 가는 가중치 ( w )의 간선

출력 형식:

  • ( 1 )번부터 ( V )번 정점까지의 최단 경로 값을 출력
  • 시작 정점은 0, 도달할 수 없는 경우는 "INF" 출력

예제 입력: 

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력: 

0
2
3
7
INF

2. 다익스트라 알고리즘 개요

다익스트라(데이크스트라) 알고리즘이란?

  • 목적:
    시작 정점에서 다른 모든 정점까지의 최단 경로를 찾기 위한 알고리즘
  • 전제 조건: 모든 간선의 가중치가 양수여야 함
  • 핵심 아이디어:
    • 탐욕적 접근: 현재까지의 최단 거리를 기준으로 가장 가까운 정점을 선택
    • 우선순위 큐(최소 힙): 정점을 효율적으로 선택하기 위해 사용

3. 정답 코드

import sys
import heapq

def dijkstra(start, graph, V):
    INF = float('inf')
    
    # 모든 정점까지의 거리를 무한대로 초기화 (시작점 제외), 왜 무한대? => 못 가게 되면 무한대로 출력하기로 문제에서 정함
    dist = [INF] * (V + 1)
    
    # 시작점의 경우 0으로 초기화
    dist[start] = 0
    
    # (거리, 정점)을 저장할 우선순위 큐(최소 힙)
    pq = []
    
    # heapq.push(pq, (거리, 정점번호)) : 튜플의 첫번째 원소를 기준으로 정렬됨.
    heapq.heappush(pq, (0, start))
    
    while pq:
        current_dist, u = heapq.heappop(pq)  # 제일 짧은 거리에 있는 녀석이 튀어나옴
        if current_dist > dist[u]:
            continue  # 이미 더 짧은 경로가발견 되었으므로 무시한다.
        
        # 정점 u에서 뻗어나가는 모든 정점 v로의 거리 갱신 시도 (간선이 여러개 있을 수 있음)
        for v, weight in graph[u]:
            if dist[v] > current_dist + weight:  # 만약 현재 거리 사전이 더 길다? 그럼
                dist[v] = current_dist + weight  # 아래처럼 갱신
                heapq.heappush(pq, (dist[v], v))
    
    return dist     
    

def main():
    V, E = map(int, sys.stdin.readline().rstrip().split())
    K  = int(sys.stdin.readline().rstrip())
    
    # 그래프 초기화 (단방향 그래프)
    graph = [[] for _ in range(V + 1)]
    
    # E: 간선의 갯수 만큼 graph 초기화 값 설정
    for _ in range(E):
        # u에서 v로 가는 가중치 w만큼의 간선
        u, v, w = map(int, sys.stdin.readline().rstrip().split())
        
        graph[u].append((v, w))
        
    distances = dijkstra(K, graph, V)
    
    for i in range(1, V + 1):
        if distances[i] == float('inf'):
            print("INF")
        else:
            print(distances[i])


if __name__ == "__main__":
    main()

4. 해설

4.1 입력 및 그래프 구성

  • 입력 처리:

    • V, E = map(int, input().split())
      → 정점 수와 간선 수를 입력받음
    • K = int(input())
      → 시작 정점을 입력받음

  • 그래프 표현:

    • graph = [[] for _ in range(V + 1)]
      → 인접 리스트 방식으로 그래프를 표현
      → 인덱스 0은 사용하지 않고 1부터 ( V )까지 사용 왜냐하면 정답 print로 뽑아낼 때 인덱스 0은 사용하지 않으니까-!

  • 간선 정보 저장:

    • 각 줄마다 u, v, w를 읽어 graph[u].append((v, w))로 저장
    • 예제 입력의 경우 아래와 같은 그래프 구조가 형성됨.

그래프 구성 표

정점 ( u )연결된 정점 ( v )와 가중치 ( w )설명
1(2, 2), (3, 3)1번에서 2번 가중치: 2, 3번 정점: 3
2(3, 4), (4, 5)2번에서 3번 가중치: 4, 4번 정점: 5
3(4, 6)3번에서 4번 가중치: 6
5(1, 1)5번에서 1번 가중치: 1

4.2 다익스트라 알고리즘 실행

4.2.1 초기화 단계

  • 거리 배열 초기화: 

    
dist = [INF] * (V + 1)
dist[start] = 0

    → 시작 정점 ( K )는 0, 나머지는 INF (아직 방문하지 않음)

  • 우선순위 큐 초기화: 

    
pq = []
heapq.heappush(pq, (0, start))

    → 튜플 (0, start)를 큐에 넣어, 시작 정점부터 처리

4.2.2 메인 루프 및 동작 흐름

루프 기본 구조:

while pq:
    current_dist, u = heapq.heappop(pq)
    if current_dist > dist[u]:
        continue
    for v, weight in graph[u]:
        if dist[v] > current_dist + weight:
            dist[v] = current_dist + weight
            heapq.heappush(pq, (dist[v], v))

설명:

  1. 우선순위 큐에서 가장 작은 거리 정점 선택:

    • heapq.heappop(pq)를 통해 (거리, 정점)을 꺼냄
    • 예: 처음에는 (0, 1) → 정점 1, 거리 0

  2. 이미 더 짧은 경로가 발견되었는지 확인:

    • if current_dist > dist[u]: continue
    • 이미 최적의 거리로 업데이트되어 있으면 해당 루프를 건너뜀
      • current_dist는 현재 진행 중인 경로의 누적 거리를 의미하는건데, 우선순위 큐를 통해서 계속해서 START지점으로 부터의 각 지점으로까지의 거리가 계속하여 갱신되어 나옴.
      • dist[u]의 경우에 u까지 이르게 되는 현재까지 발견된 최단거리를 의미하는데, 만약 current_dist가 이미 기록된 dist[u]보다 크다면, 그건 정점 u까지 도달하는더 짧은 경로가 이미 발견되었으므로, 지금 꺼낸 경로(current_dist)가 쓸모없게 되었다는 얘기임.
      • 즉, current_dist가 dist[u]보다 크다면, 어차피 이 경로는 더 짧은 경로를 갱신할 가능성이 전혀 없기에 그냥 무시(continue)하라는 것.

  3. 현재 정점 u의 인접 정점 v들에 대해 거리 갱신:

    • 조건 확인: 만약 dist[v] > current_dist + weight이면
    • 업데이트: dist[v]를 새로운 거리로 갱신하고, (dist[v], v)를 큐에 추가

4.3 루프 진행 및 우선순위 큐 변화

초기 상태

상태 변수값
dist[INF, 0, INF, INF, INF, INF]
pq[(0, 1)]

1. 정점 1 처리

  • 우선순위 큐: pq.pop() → (0, 1)
  • 정점 1의 인접 정점:
    • (2, 2):
      • 기존 dist[2] = INF → 새 거리 0+2 = 2로 갱신
      • heapq.heappush(pq, (2, 2))
    • (3, 3):
      • 기존 dist[3] = INF → 새 거리 0+3 = 3로 갱신
      • `heapq.heappush(pq, (3, 3))
정점갱신 전 거리계산된 거리갱신 후 거리큐 추가 항목
2INF0 + 2 = 22(2, 2)
3INF0 + 3 = 33(3, 3)

상태 변화

상태 변수값
dist[INF, 0, 2, 3, INF, INF]
pq[(2, 2), (3, 3)]

2. 정점 2 처리

  • 우선순위 큐: pq.pop() → (2, 2)
  • 정점 2의 인접 정점:
    • (3, 4):
      • 기존 dist[3] = 3 → 계산된 거리 2+4 = 6 (갱신 불필요)
    • (4, 5):
      • 기존 dist[4] = INF → 계산된 거리 2+5 = 7로 갱신
      • heapq.heappush(pq, (7, 4))
정점갱신 전 거리계산된 거리갱신 후 거리큐 추가 항목
332 + 4 = 63 (유지)-
4INF2 + 5 = 77(7, 4)

상태 변화

상태 변수값
dist[INF, 0, 2, 3, 7, INF]
pq[(3, 3), (7, 4)]

3. 정점 3 처리

  • 우선순위 큐: pq.pop() → (3, 3)
  • 정점 3의 인접 정점:
    • (4, 6):
      • 기존 dist[4] = 7 → 계산된 거리 3+6 = 9 (갱신 불필요)
정점갱신 전 거리계산된 거리갱신 후 거리큐 추가 항목
473 + 6 = 97 (유지)-

상태 변화

상태 변수값
dist[INF, 0, 2, 3, 7, INF]
pq[(7, 4)]

4. 정점 4 처리

  • 우선순위 큐: pq.pop() → (7, 4)
  • 정점 4의 인접 정점:
    • 없음 → 추가 작업 없음
      상태 변수값
      dist[INF, 0, 2, 3, 7, INF]
      pq[] (빈 상태)

→ 큐가 비었으므로 while 루프 종료

5. 최종 출력

루프 종료 후 dist 배열 상태는 다음과 같음.

정점 번호최단 거리설명
10시작 정점 (항상 0)
22경로: 1 → 2 (거리 2)
33경로: 1 → 3 (거리 3)
47경로: 1 → 2 → 4 (거리 2+5 = 7)
5INF1번 정점에서 도달 불가 → "INF" 출력

최종 출력:

0
2
3
7
INF

6. 결론

  • 입력 처리 및 그래프 구성:

    • 인접 리스트를 사용해 ( u )에서 ( v )로의 간선 정보를 저장하는 것을 먼저 처리하고

  • 다익스트라 알고리즘:

    • 시작 정점부터 모든 정점까지의 최단 거리를 구하는 탐욕적 방법을 사용하여
    • 우선순위 큐(최소 힙)를 사용해 가장 짧은 경로를 우선적으로 처리함.
    • 이미 최단 경로가 갱신된 정점은 continue를 통해 건너뛰어 불필요한 연산을 줄임.

  • 루프 진행 및 우선순위 큐 변화:

    • 각 루프에서 현재 최단 거리를 가진 정점을 선택하고, 인접 정점들의 최단 거리를 갱신.
    • 표를 통해 각 단계에서의 dist 배열과 pq의 변화를 확인해 볼 것
profile
SeongGyun Hong
헤매는 만큼 자기 땅이다.
이전 포스트

BFS: 백준 13549 오답노트

다음 포스트

Back Track: 백준 9663 오답노트

0개의 댓글