크래프톤 정글 캠퍼스에서 캐리비안베이로 가는 제일 빠른 길은??

실내 교육장에만 있다 보니 웃통 까고 선탠하고 싶습니다.

농담입니다. 예쁜 래시가드 입겠습니다.

좌우지간, 최단 경로 알고리즘에 대해 알아봅시다.

최단 경로 문제

• 가장 짧은 경로를 찾는 알고리즘

  • e.g., 한 노드에서 다른 한 노드까지의 최단 경로 구하기
  • e.g., 한 노드에서 다른 모든 노드까지의 최단 경로 구하기
  • e.g., 모든 노드에서 다른 모든 노드까지 최단 경로를 모두 구함

  

• 최단 경로: 이동한 간선의 가중치 합이 최저값인 경로
  ⚠️ 보통 간선의 가중치 합을 거리라고 합니다.

알고리즘	언제?	시간 복잡도 (노드수 $N$ 간선수 $E$)
BFS	가중치가 명시되지 않은 경우 한 노드 -> 모든 노드 간 거리	$O(N + E)$
다익스트라	0 이상의 가중치가 명시된 경우 한 노드 -> 모든 노드 간 거리	$O(E \log N)$
플로이드 워셜	모든 노드 -> 모든 노드 간 거리	$O(N^3)$

BFS

• 가중치가 명시되지 않은 경우, 거치는 간선 개수가 가장 적은 경로가 최단 경로
• BFS의 가까운 노드부터 방문하는 성질을 이용해, 최단 경로 계산 가능
• BFS로 노드를 방문할 때마다, 출발 노드와의 거리를 계산. 이 글 18352번 문제풀이 보는 거 추천.

다익스트라 알고리즘

• 특정 노드에서 출발해서, 다른 모든 노드로 가는 최단 경로 계산
• 음의 가중치를 가진 간선이 없을 때 정상적으로 동작
• 매 상황에서 가장 가중치가 적은 노드를 선택하는 과정을 반복
  • 매 순간 최선의 선택을 하는, 일종의 그리디 알고리즘

⚠️ 음의 가중치를 가진 간선이 있는 경우, 벨만-포드 알고리즘을 사용합니다. 이 글에선 다루지 않습니다.

과정

• (1) 출발 노드를 설정
• (2) 최단 거리 테이블을 초기화
  • 각 노드에 대해, 출발 노드로부터의 최단 거리 정보를 저장
  • 기본값은 무한, 출발 노드 자기 자신은 0으로 초기화
  • 이후 처리 과정에서 더 짧은 경로를 찾으면, 정보를 갱신

• (3) 방문하지 않은 노드 중, 최단 거리가 가장 짧은 노드 방문

  • cf. 방문한 노드의 최단거리는 확정되며, 더 이상 갱신되지 않음
  • 뭐라 설명하기가 애매해서, 직접 아래 사진 보고 이해하는 걸 추천합니다.

• (4) 현재 노드와 인접한 노드들 확인

  • 인접 노드들까지의 최단 거리를 계산한 뒤, 기존 값보다 작으면 갱신
  • (현재 노드의 최단거리 테이블 값) + (현재 노드와 인접 노드의 간선 가중치)

(4 -> 5)까지의 거리 2 -> 1로 수정합니다. 즉 합산 거리는 3이 아니라 2가 되겠죠

• (5): (3), (4)를 모든 노드를 방문할 때까지 반복

구현

INF = float('inf')  # 무한의 값

# 각 노드와 연결된 노드를 인접 리스트로 관리
# (도착 노드, 비용)
graph = [
    [],
    [(2, 2), (4, 1)],
    [(3, 3), (4, 2)],
    [(2, 3), (6, 5)],
    [(3, 3), (5, 1)],
    [(3, 1), (6, 2)],
    []
]

N = len(graph) - 1
visited = [False] * (N + 1)     # 방문 여부 확인
dist_table = [INF] * (N + 1)          # 최단 거리 테이블

• visited 리스트로 방문 여부 확인
  • visited[i] = True일 시 i번노드 방문, 아닐 시 방문 X
• float('inf') 로 무한 값 사용 가능

# 방문하지 않은 노드 중, 가장 최단거리가 짧은 노드의 번호 반환
def shortest_node():
    min_dist = INF
    min_node = 0
    for i in range(1, N + 1):
        if dist_table[i] < min_dist and not visited[i]:
            min_dist = dist_table[i]
            min_node = i
    return min_node

# 다익스트라 알고리즘
def djikstra(start):
    dist_table[start] = 0     # 출발 노드의 최단거리는 0

    # 각 노드에 대해서...
    for _ in range(N):
        i = shortest_node()
        visited[i] = True

        # 인접 노드의 거리 갱신
        # j: 인접노드 번호, j_dist: 간선 비용
        for j, j_dist in graph[i]:
            cost = dist_table[i] + j_dist
            if cost < dist_table[j]:
                dist_table[j] = cost

• 최단거리가 가장 짧은 노드를 구할 땐, dist_table 리스트의 모든 값을 탐색하여 최솟값을 구함
• 거리 계산 -> dist_table[i] (출발 노드 -> i 노드) + j_dist (i 노드 -> 인접 j 노드)

djikstra(1)

for i in range(1, N + 1):
    if dist_table[i] == INF:
        print("X")
    else:
        print(f"노드 {i} 최단거리: {dist[i]}")

# 노드 1 최단거리: 0
# 노드 2 최단거리: 2
# 노드 3 최단거리: 3
# 노드 4 최단거리: 1
# 노드 5 최단거리: 2
# 노드 6 최단거리: 4

시간 복잡도

• 노드 수가 $N$개일 때, shortest_node 함수로 현재 최단 거리의 노드를 선형 탐색할 때 $O(N)$
• 총 $N$번 shortest_node 함수가 실행되므로 $O(N^2)$
• 더 빠른 방법은 없을까요?

우선순위 큐를 이용한 다익스트라 알고리즘 구현

• 매번 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해, 최소 힙을 사용
• 노드의 최단 거리를 갱신할 때마다, 우선순위 큐에 (거리, 노드) 꼴의 튜플 삽입

과정

• (1) 출발 노드를 설정
  • 우선순위 큐에 (0, 출발 노드) 삽입
• (2) 최단 거리 테이블을 초기화 -> 기존과 동일

• (3) 우선순위 큐에서 원소를 팝
  • 최소 힙 특성상, 매번 최단 거리가 가장 짧은 노드 원소를 반환
  • cf. 팝한 노드의 최단거리는 확정되며, 더 이상 갱신되지 않음
• (4) 팝한 노드와 인접한 노드들 확인
  • 최단 거리가 갱신된 노드에 대해선, (거리, 노드) 튜플을 우선순위 큐에 푸시
• 단, (3)에서 더 짧은 거리로 이미 방문한 노드를 팝한 경우 건너뜀
  • ⚠️ e.g., 최단거리 테이블 dist[A] = 3인데 큐에서 (5, A)가 팝된 경우
  • 거리 비교로 방문 여부를 확인 가능하므로, visited 배열이 필요 없음

• (5) 큐가 빌 때까지 반복

제가 모르고 #6을 건너뛰고 #7로 적어 놨군요. 사진 하나가 빠진 건 아니니 걱정마십쇼.

코드

import heapq
import sys
input = sys.stdin.readline
INF = float('inf')

# 각 노드와 연결된 노드를 인접 리스트로 관리
# (도착 노드, 비용)
graph = [
    [],
    [(2, 2), (4, 1)],
    [(3, 3), (4, 2)],
    [(2, 3), (6, 5)],
    [(3, 3), (5, 1)],
    [(3, 1), (6, 2)],
    []
]

N = 6

# 최단 거리 테이블
dist_table = [INF] * (N + 1)

• visited 리스트가 없는 것 빼고 동일

def djikstra(start):
    queue = []

    # 시작 노드를 큐에 삽입 및 거리 0으로 설정
    heapq.heappush(queue, (0, start))
    dist_table[start] = 0

    while queue:
        # 가장 최단 거리가 짧은 노드 i 꺼내기
        i_dist, i = heapq.heappop(queue)

        # 이미 더 짧은 거리로 방문한 경우 무시
        if i_dist > dist_table[i]:
            continue

        # i의 인접 노드 j 확인
        for j, j_dist in graph[i]:
            # j: 인접 노드, j_dist: 간선 가중치
            # 현재 노드를 거쳐, 인접 노드로 이동하는 거리
            new_dist = i_dist + j_dist

            # 거리가 더 짧으면 갱신
            if new_dist < dist_table[j]:
                dist_table[j] = new_dist
                heapq.heappush(queue, (new_dist, j))

• 우선순위 큐 queue에 거리가 갱신될 때마다 (거리, 노드번호) 푸시
  • 우선순위 큐에 튜플을 푸시하는 경우, 첫 값을 우선적으로 최솟값을 반환

시간 복잡도

• 노드 수가 $N$, 간선 수가 $E$일 때
• 힙 푸시, 팝 등 우선순위 큐 연산은 시간 복잡도는 $O(\log E)$
• 인접 리스트의 원소를 확인하면서 힙 푸시, 팝 진행
  • 최악의 경우 $E$개의 간선을 모두 푸시/팝하게 되므로 $O(E \log E)$
• 중복된 간선이 없는 경우 (즉 두 노드를 연결하는 간선이 유일한 경우)
  • $E \leq N^2$ ($N^2$: 각 노드가 모든 다른 노드와 연결되어 있을 때 총 간선 수)
  • 따라서 $O(E \log E) = O(E \log N^2) = O(2E \log N) = O(E \log N)$

플로이드 워셜 알고리즘

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산
• 2차원 테이블에 최단 거리 정보를 저장
  • dist_table[i][j] -> 노드 i부터 j까지 최단 거리
• 각 단계마다 특정 노드 $k$를 거쳐 가는 경우 확인
  • 현재 2차원 테이블에 기록된 $i$ -> $j$의 최단 거리보다
  • $i$에서 $k$를 거쳐 $b$로 가는 거리가 더 짧으면 갱신
  • dist_table[i][j] = min(dist_table[i][j], dist_table[i][k] + dist_table[k][j])

과정

• (1) 최단 거리 테이블을 초기화
  • 두 노드 간 간선의 가중치로 초기화
  • 자기 자신과의 거리는 0
  • 간선이 없는 경우 무한

• (2) 각 노드 k를 거쳐 가는 경우를 고려하여 테이블을 갱신
  • 출발 노드를 i, 도착 노드를 j라 할 때
  • i -> k + k -> j 간 거리가 기존 i -> j 간 거리보다 가까우면 갱신

구현

INF = float('inf')

# 그래프의 인접 행렬 표현
dist_table = [
    [INF, 4, INF, 6],
    [3, INF, 7, INF],
    [5, INF, INF, 4],
    [INF, INF, 2, INF]
]

N = 4

# 자기 자신과의 거리는 0
for i in range(N):
    for j in range(N):
        if i == j:
            dist_table[i][j] = 0

• 기존 인접 행렬 표현은 자기 자신과의 거리도 무한으로 표시했음에 유의
• 즉, 자기 자신과의 거리는 0으로 변경
• 플로디드 워셜은 매번 두 임의의 노드 간 비용을 계산해야 하므로, 인접 행렬을 이용해 구현하는 게 유리함

# 플로이드 와셜 알고리즘 수행
for k in range(N):          # 중간 노드
    for i in range(N):      # 출발 노드
        for j in range(N):  # 도착 노드
            dist_table[i][j] = min(dist_table[i][j], dist_table[i][k] + dist_table[k][j])

• 3중 반복문을 이용해, 각 노드 k에 대해
• i -> k -> j의 경로가 기존 i -> j의 경로보다 짧으면 값을 갱신

# 결과 출력
for i in range(N):
    for j in range(N):
        if dist_table[i][j] == INF:
            print(f"{'X':4}", end = "")
        else:
            print(f"{dist_table[i][j]:4}", end="")
    print()

#    0   4   8   6
#    3   0   7   9
#    5   9   0   4
#    7  11   2   0

시간 복잡도

• 노드의 개수가 $N$개일 때 총 $N$단계
  • 각 단계에서 $O(N^2)$ 연산을 통해, 모든 경로를 고려
• 최종 $O(N^3)$ (삼중 반복문)

문제풀이

1916. 최소비용 구하기

백준 / 골드 5 / 1916. 최소비용 구하기

• 가중치가 다른 간선이 주어졌으며, 출발점에서 도착점까지 위치를 구해야 하므로 다익스트라 사용

import heapq
import sys
input = sys.stdin.readline

N = int(input())
M = int(input())

INF = float('inf')
graph = [[] for _ in range(N + 1)] # 인접리스트
dist_table = [INF] * (N + 1)             # 거리 정보

# 인접 리스트 만들기: (노드, 가중치)
for _ in range(M):
    a, b, dist = map(int, input().split())
    graph[a].append((b, dist))

chulbal, dochak = map(int, input().split())

# 다익스트라 알고리즘
def djikstra(chulbal, dochak, graph, dist):
    queue = []
    
    # (최소비용, 노드)
    heapq.heappush(queue, (0, chulbal))
    dist_table[chulbal] = 0
    
    while queue:
        i_cost, i = heapq.heappop(queue)
        if i_cost > dist_table[i]:
            continue
        
        if i == dochak:
            return i_cost
        
        for j, j_cost in graph[i]:
            new_cost = i_cost + j_cost
            if new_cost < dist_table[j]:
                dist_table[j] = new_cost
                heapq.heappush(queue, (new_cost, j))
                
print(djikstra(chulbal, dochak, graph, dist_table))

• 단방향 그래프이므로 graph[a].append((b, dist)) 한 쪽만 저장하면 됨
• 우선순위 큐에서 꺼낸 노드가 도착 노드인 경우
  • 우선순위 큐에서 노드를 팝할 때, 해당 노드의 최단 거리는 확정됨
  • 즉 더 이상 추가로 불필요한 개선을 할 필요는 없음
  • 따라서 바로 i_cost를 반환해도 됨

11404. 플로이드

백준 / 골드 4 / 11404. 플로이드

• 모든 지점에서 모든 지점 간 최단 거리를 구해야 하니, 플로이드 워셜 알고리즘을 사용
  • 사실 제목부터 스포하고 있잖아요..
• 단 이 문제에서는 노드 간 간선이 여러개일 수 있음
  • 맨 처음 인접 행렬을 만들 때, 그 중 최소 비용인 간선만 남겨 놓아야 함

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
INF = float('inf')

graph = [[INF] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a][b] = min(graph[a][b], c)
    
for i in range(1, N + 1):
    graph[i][i] = 0
    

for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

          
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if graph[i][j] >= INF:
            print(0, end=" ")
        else:
            print(graph[i][j], end = " ")
    print()