코딩테스트

[코테] 최단 경로

하방주인장 2025. 3. 4. 11:03

목차

    📍 최단 경로란 무엇인가?

    최단 경로(Shortest Path)는 그래프에서 가장 짧은 경로를 찾는 알고리즘입니다. 일상 생활에서 경험하는 '길 찾기' 문제와 같아서 이렇게 불리기도 합니다. 그래프에서 각 지점은 '노드'로, 지점 간 연결된 도로는 '간선'으로 표현됩니다.

    최단 경로 문제는 다양한 형태로 나타납니다:

    • 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우
    • 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 경우

    실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다, 단순히 최단 거리만 출력하도록 요구하는 경우가 많습니다.

    🔍 다익스트라(Dijkstra) 최단 경로 알고리즘

    기본 개념

    다익스트라 알고리즘은 특정 노드에서 출발해 다른 모든 노드로 가는 각각의 최단 경로를 구하는 알고리즘입니다. 이 알고리즘은 '음의 간선이 없을 때' 정상적으로 작동합니다. 음의 간선이란 가중치가 0보다 작은 간선을 의미합니다.

    현실 세계의 길(간선)은 대부분 양의 값을 가지므로, 다익스트라 알고리즘은 실제 GPS 소프트웨어의 기본 알고리즘으로 많이 사용됩니다.

    다익스트라 알고리즘은 그리디 알고리즘?

    다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류됩니다. 매번 '가장 비용이 적은 노드'를 선택해 과정을 반복하기 때문입니다. 알고리즘의 원리는 다음과 같습니다:

    1. 출발 노드를 설정합니다.
    2. 최단 거리 테이블을 초기화합니다.
    3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택합니다.
    4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.
    5. 3번과 4번 과정을 반복합니다.

    다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 지속적으로 갱신합니다.

    다익스트라 알고리즘 구현 방법

    다익스트라 알고리즘을 구현하는 방법은 크게 두 가지입니다:

    1. 구현하기 쉽지만 느리게 동작하는 방법
    2. 구현이 까다롭지만 빠르게 동작하는 방법 (우선순위 큐 활용)

    시험을 준비하는 분들은 두 번째 방법을 정확히 이해하고 구현할 수 있을 때까지 연습하는 것이 좋습니다. 최단 경로 알고리즘은 응용해서 풀 수 있는 고난이도 문제가 많기 때문입니다.

    다익스트라 알고리즘 작동 과정 예시

    예를 들어, 다음과 같은 그래프에서 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구해봅시다.

    Step 1:

    • 출발 노드(1번)에서 출발 노드로의 거리는 0으로 설정
    • 1번 노드를 거쳐 2번, 3번, 4번 노드로 가는 비용을 계산
      • 1→2: 2 (0+2)
      • 1→3: 5 (0+5)
      • 1→4: 1 (0+1)
    • 최단 거리 테이블 갱신

    Step 2:

    • 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드(4번) 선택
    • 4번 노드를 거쳐 갈 수 있는 노드(3번, 5번) 확인
      • 4→3: 4 (1+3)
      • 4→5: 2 (1+1)
    • 최단 거리 테이블 갱신

    이런 방식으로 모든 노드에 대한 최단 거리를 구할 때까지 반복합니다.

    👨‍💻 방법 1: 간단한 다익스트라 알고리즘 구현

    간단한 다익스트라 알고리즘은 직관적이고 이해하기 쉽습니다. 각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언하고, 매 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택합니다.

     

    import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억 설정

# 노드의 개수, 간선의 개수 입력받기
n, m = map(int, input().split())
# 시작 노드 번호 입력받기
start = int(input())
# 각 노드에 연결된 노드 정보를 담는 리스트
graph = [[] for i in range(n + 1)]
# 방문 여부 체크 리스트
visited = [False] * (n + 1)
# 최단 거리 테이블을 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c
    graph[a].append((b, c))

# 방문하지 않은 노드 중 가장 최단 거리가 짧은 노드 번호 반환
def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n + 1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    # 시작 노드 초기화
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    # 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
    for i in range(n - 1):
        # 현재 최단 거리가 가장 짧은 노드 꺼내서 방문 처리
        now = get_smallest_node()
        visited[now] = True
        # 현재 노드와 연결된 다른 노드 확인
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]]:
                distance[j[0]] = cost

# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

    시간 복잡도

    간단한 다익스트라 알고리즘의 시간 복잡도는 O(V²)입니다. 여기서 V는 노드의 개수를 의미합니다. 매번 최단 거리가 가장 짧은 노드를 선형 탐색하고, 현재 노드와 연결된 노드를 일일이 확인하기 때문입니다.

    따라서 노드의 개수가 5,000개 이하라면 이 방법으로 해결할 수 있지만, 10,000개를 넘어가면 개선된 알고리즘을 사용해야 합니다.

    🚀 방법 2: 개선된 다익스트라 알고리즘 (우선순위 큐 활용)

    개선된 다익스트라 알고리즘은 시간 복잡도를 O(ElogV)로 줄일 수 있습니다. 여기서 E는 간선의 개수, V는 노드의 개수입니다. 이를 위해 '힙(Heap)' 자료구조를 활용합니다.

    힙(Heap)과 우선순위 큐(Priority Queue)

    힙 자료구조는 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나입니다. 우선순위 큐는 '우선순위가 가장 높은 데이터를 가장 먼저 삭제'하는 특징이 있습니다.

    스택(Stack) 가장 나중에 삽입된 데이터
    큐(Queue) 가장 먼저 삽입된 데이터
    우선순위 큐(Priority Queue) 가장 우선순위가 높은 데이터

    파이썬에서는 우선순위 큐를 구현하기 위해 PriorityQueue 또는 heapq를 사용할 수 있습니다. 일반적으로 heapq가 더 빠르게 동작하므로 코딩 테스트에서는 heapq를 사용하는 것이 좋습니다.

    개선된 다익스트라 알고리즘 구현

    import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

# 노드의 개수, 간선의 개수 입력받기
n, m = map(int, input().split())
# 시작 노드 번호 입력받기
start = int(input())
# 각 노드에 연결된 노드 정보를 담는 리스트
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        # 가장 최단 거리가 짧은 노드 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적 있으면 무시
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 다른 인접 노드들 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

    시간 복잡도 분석

    개선된 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)입니다:

    • 한 번 처리된 노드는 더 이상 처리되지 않으므로, 큐에서 노드를 꺼내는 작업은 최대 V번 수행됩니다.
    • 각 노드가 연결된 간선을 모두 확인하는 작업은 총 E번 수행됩니다.
    • 우선순위 큐에 원소를 삽입하거나 삭제하는 연산은 logE(혹은 logV) 시간이 걸립니다.

    따라서 전체 시간 복잡도는 O(ElogV)가 되어, 간단한 다익스트라 알고리즘보다 훨씬 효율적입니다.

    🧩 플로이드 워셜(Floyd-Warshall) 알고리즘

    기본 개념

    플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로'를 구하는 알고리즘입니다. 다익스트라 알고리즘과 달리, 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 방식을 사용합니다.

    다익스트라 알고리즘이 출발점이 1개일 때 사용한다면, 플로이드 워셜 알고리즘은 모든 노드 쌍 사이의 최단 경로를 한 번에 계산합니다.

    동작 원리

    플로이드 워셜 알고리즘은 각 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행합니다:

    1. 2차원 리스트에 최단 거리 정보를 저장합니다.
    2. 각 노드를 하나씩 거쳐 가는 경우를 고려하여 최단 거리를 갱신합니다.
    3. 노드 k를 거쳐 가는 경우, a에서 b로 가는 최단 거리를 다음과 같이 갱신합니다:
      • D[a][b] = min(D[a][b], D[a][k] + D[k][b])

    플로이드 워셜 알고리즘 구현

    INF = int(1e9)  # 무한을 의미하는 값으로 10억 설정

# 노드의 개수 및 간선의 개수 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    # A에서 B로 가는 비용은 C라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if graph[a][b] == INF:
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end=" ")
    print()

    시간 복잡도

    플로이드 워셜 알고리즘의 시간 복잡도는 O(N³)입니다. 3중 반복문을 사용하기 때문입니다. 따라서 노드의 개수가 적은 문제(약 500개 이하)에 적합합니다.

    📊 최단 경로 알고리즘 비교 및 선택 기준

    간단한 다익스트라 O(V²) 노드 수가 적은 경우(5,000개 이하)
    개선된 다익스트라(우선순위 큐) O(ElogV) 노드 수가 많은 경우, 한 지점에서 다른 모든 지점
    플로이드 워셜 O(N³) 모든 지점에서 모든 지점, 노드 수가 적은 경우(500개 이하)

    알고리즘 선택 기준

    1. 다익스트라 알고리즘:
      • 한 지점에서 다른 지점까지의 최단 경로
      • 음의 간선이 없는 경우
      • 노드 수가 많은 경우 개선된 다익스트라(우선순위 큐) 사용
    2. 플로이드 워셜 알고리즘:
      • 모든 지점에서 모든 지점까지의 최단 경로
      • 노드 수가 적은 경우(500개 이하)
      • 구현이 상대적으로 간단하나 시간 복잡도가 높음

    🔑 핵심 개념 정리

    1. 최단 거리 테이블: 각 노드까지의 최단 거리를 저장하는 배열
    2. 무한(INF): 연결되지 않은 노드 간 거리, 보통 매우 큰 값(10억 등)으로 초기화
    3. 우선순위 큐: 가장 비용이 적은 노드를 빠르게 찾기 위한 자료구조
    4. 점화식: 플로이드 워셜에서 D[a][b] = min(D[a][b], D[a][k] + D[k][b])

    🌟 마치며

    최단 경로 알고리즘은 GPS 네비게이션, 네트워크 라우팅, 게임 개발 등 실생활의 다양한 문제를 해결하는 데 활용됩니다. 각 알고리즘의 특성과 적용 상황을 이해하고, 문제에 맞는 알고리즘을 선택하여 효율적으로 구현하는 능력을 기르는 것이 중요합니다.

    코딩 테스트에서 최단 경로 문제는 자주 출제되는 유형 중 하나이니, 다익스트라 알고리즘과 플로이드 워셜 알고리즘의 구현 방법을 충분히 숙지하고 연습하시길 바랍니다.

    저작자표시 비영리 변경금지