문제해결 프로그래밍

최단 경로 문제

강원대학교 컴퓨터공학과 최우혁

강의 순서

• 최단 경로 문제Shortest Path Problem
• 문제: 소방서Fire Station
• 문제: 황혼에서 새벽까지From Dusk Till Dawn
• 문제: 티모의 여행Teemo’s Trip

2

최단 경로 문제Shortest Path Problem

3

최단 경로 문제?

최단 경로 문제Shortest Path Problem

• 그래프Connected Graph 내에 존재하는 한 정점에서 다른 정점으로 가는 경로 중 가장 짧은 경로와 그 길이를 찾는 문제
• 다양한 그래프에서 최단 경로 문제가 정의됨
• 비방향 그래프Undirected Graph
• 가중치가 없는 그래프Unweighted Graph
• 가중치가 있는 방향 그래프Weighted Digraph
• 가중치가 0 이상인 방향 그래프Directed Graph with Non-negative Weights
• 임의의 가중치를 가지면서 순환 경로의 거리가 0 이상인 그래프Directed Graph with Arbitrary Weights with Negative Cycles
• 임의의 가중치를 가지면서 순환 경로의 거리가 음수인 그래프Directed Graph with Arbitrary Weights with Negative Cycles

4

최단 경로 문제의 종류

최단 경로 문제Shortest Path Problem

• 단일 출발점 최단 경로 문제Single-source Shortest Path Problem
• 그래프의 주어진 한 정점에서 출발하여 각 정점으로 도착하는 최단 경로 및 그 거리를 구하는 문제
• 단일 도착점 최단 경로 문제Single-destination Shortest Path Problem
• 그래프의 각 정점에서 출발하여 주어진 한 정점으로 도착하는 최단 경로 및 그 거리를 구하는 문제
• 전쌍 최단 경로 문제All-pairs Shortest Path Problem
• 그래프의 각 정점에서 출발하여 다른 각 정점으로 도착하는 최단 경로 및 그 거리를 구하는 문제

5

단일 출발점 최단 경로 문제를 푸는 대표적 알고리즘

최단 경로 문제Shortest Path Problem

• 방향이 없는 그래프Undirected Graph
• 다익스트라Dijkstra의 알고리즘
• 가중치가 없는 그래프Unweighted Graph
• 너비 우선 탐색Breadth-first Search
• 가중치가 0 이상인 방향 그래프Directed Graph with Non-negative Weights
• 다익스트라Dijkstra의 알고리즘
• 임의의 가중치를 가지면서 순환 경로의 거리가 0 이상인 그래프Directed Graph with Arbitrary Weights with Negative Cycles
• 다익스트라Dijkstra의 알고리즘

6

다익스트라Dijkstra의 알고리즘

최단 경로 문제Shortest Path Problem

• 문제: 가중치 포함 방향 그래프에서 v₀에서 출발하여 다른 모든 정점으로 가는 최단 경로 및 최단 경로의 길이를 구하라
• 입력: 가중치 포함 방향 그래프 인접 리스트 G, 정점의 개수 n
• 출력: v₀에서 다른 모든 정점으로 가는 최단 경로 길이 배열 D 및 최단 경로를 출력하기 위해 부모 정점을 저장하는 배열 P
• 아이디어
• 모든 정점의 집합 V와 최단 경로를 찾은 정점들의 집합 Y에 대해, Y에 있는 정점과 간선으로 연결된 V − Y에 속한 정점들(최단 경로를 찾지 못한 정점) 중 가장 가까운 정점 하나를 선정

7

다익스트라Dijkstra의 알고리즘: 구현

최단 경로 문제Shortest Path Problem

8

1 import sys

2 import heapq

3

4

5 def dijkstra(G, n):

6 D = [sys.maxsize for _ in range(n)]

7 Y = [False for _ in range(n)]

8 P = [0 for _ in range(n)]

9 Q = []

10

11 D[0] = 0

12 heapq.heappush(Q, (0, 0))

13

14 while Q:

15 d, v = heapq.heappop(Q)

16 Y[v] = True

17 for u, w in G[v].items():

18 if not Y[u] and d + w < D[u]:

19 heapq.heappush(Q, (d + w, u))

20 D[u] = d + w

21 P[u] = v

22

23 return D, P

1 from collections import deque

2

3

4 def path_reconstruction(P, v):

5 path = deque([v])

6 while v != 0:

7 v = P[v]

8 path.appendleft(v)

9 return path

다익스트라Dijkstra의 알고리즘: 예

최단 경로 문제Shortest Path Problem

9

다익스트라Dijkstra의 알고리즘: 예

최단 경로 문제Shortest Path Problem

10

다익스트라Dijkstra의 알고리즘: 예

최단 경로 문제Shortest Path Problem

11

다익스트라Dijkstra의 알고리즘: 예

최단 경로 문제Shortest Path Problem

12

다익스트라Dijkstra의 알고리즘: 예

최단 경로 문제Shortest Path Problem

13

다익스트라Dijkstra의 알고리즘: 경로 출력의 예

최단 경로 문제Shortest Path Problem

• v₀ → v₇
• p = [v₇]
• p = [P[7] = v₃, v₇]
• p = [P[3] = v₂, v₃, v₇]
• p = [P[2] = v₁, v₂, v₃, v₇]
• p = [P[1] = v₀, v₁, v₂, v₃, v₇]

14

1 from collections import deque

2

3

4 def path_reconstruction(P, v):

5 path = deque([v])

6 while v != 0:

7 v = P[v]

8 path.appendleft(v)

9 return path

전쌍 최단 경로 문제를 푸는 대표적 알고리즘

최단 경로 문제Shortest Path Problem

• 방향이 없는 그래프Undirected Graph
• 플로이드Floyd의 알고리즘
• 가중치가 없는 그래프Unweighted Graph
• 플로이드Floyd의 알고리즘
• 가중치가 0 이상인 방향 그래프Directed Graph with Non-negative Weights
• 플로이드Floyd의 알고리즘
• 임의의 가중치를 가지면서 순환 경로의 거리가 0 이상인 그래프Directed Graph with Arbitrary Weights with Negative Cycles
• 플로이드Floyd의 알고리즘

15

플로이드Floyd의 알고리즘

최단 경로 문제Shortest Path Problem

• 문제: 가중치 포함 방향 그래프에서 각 정점에서 자신을 제외한 다른 정점들까지 가는 경로 중 최단 경로의 길이를 찾아라
• 입력: 가중치 포함 방향 그래프 W, 정점의 개수 n
• 출력: 각 정점에서 다른 모든 정점으로 가는 최단 경로 길이 행렬 D 및 최단 경로 출력을 위해 방문하는 정점을 저장하는 행렬 P

​

16

플로이드Floyd의 알고리즘: 아이디어

최단 경로 문제Shortest Path Problem

• 동적 계획법: 최단 경로를 찾는 재귀 관계를 찾아서 해결함
• 예. 이항계수를 계산하는 재귀 관계

​

​

• 2차원 배열 B를 만들고, C(i, j)의 결과를 B[i][j]에 저장
• 작은 입력사례 (즉, B[0][0]) 부터 차례대로 계산해서, 최종적으로 B[n][k]를 계산

17

플로이드Floyd의 알고리즘: 아이디어

최단 경로 문제Shortest Path Problem

• 최단 경로의 길이를 저장하는 3차원 행렬 D를 정의
• D[k][i][j]: {v₁, v₂, … , v_k}의 정점들 중 일부를 거치며 v_i부터 v_j로 가는 최단 경로의 길이
• D[0][i][j] = W[i][j]: 아무런 정점을 거치지 않고 v_i에서 v_j로 가는 최단 경로의 길이이므로, 즉 v_i와 v_j를 연결하는 간선의 가중치
• D[n][i][j]: n개의 모든 정점들 중 일부를 거쳐서 v_i에서 정점 v_j로 가는 최단 경로의 길이
• 즉, D[k][i][j]를 D[k-1][i][j]로 표현하는 재귀 관계를 찾아야 함

18

플로이드Floyd의 알고리즘: 재귀 관계의 예

최단 경로 문제Shortest Path Problem

19

플로이드Floyd의 알고리즘: 재귀 관계의 예

최단 경로 문제Shortest Path Problem

20

플로이드Floyd의 알고리즘: 재귀 관계의 예

최단 경로 문제Shortest Path Problem

21

플로이드Floyd의 알고리즘: 재귀 관계의 예

최단 경로 문제Shortest Path Problem

22

플로이드Floyd의 알고리즘: 재귀 관계의 예

최단 경로 문제Shortest Path Problem

23

플로이드Floyd의 알고리즘: 재귀 관계의 예

최단 경로 문제Shortest Path Problem

24

플로이드Floyd의 알고리즘: 재귀 관계

최단 경로 문제Shortest Path Problem

• D[k-1][i][j]와 D[k][i][j]간의 관계: (1) 정점 v_k을 추가해도 값의 변화가 없음
• 추가한 정점이 자기 자신
• 추가한 정점을 포함하는 최단 경로가 없음

​

​

​

25

D[k][i][j] = D[k-1][i][j]

플로이드Floyd의 알고리즘: 재귀 관계

최단 경로 문제Shortest Path Problem

• D[k-1][i][j]와 D[k][i][j]간의 관계: (2) 중간 정점 v_k을 추가하면 길이의 변화, 즉, 더 짧은 경로를 발견
• 최단 경로 v_i → v_j 사이에 중간 정점 v_k가 있을때, 이 경로의 길이는 최단 경로 v_i → v_k의 길이와 최단 경로 v_k → v_j의 길이의 합임
• 당연히, 최단 경로 v_i → v_k와 최단 경로 v_k → v_j는 v_k를 중간 정점으로 포함하지 않음(즉, D[k-1])

​

​

26

D[k][i][j] = D[k-1][i][k] + D[k-1][k][j]

플로이드Floyd의 알고리즘: 재귀 관계

최단 경로 문제Shortest Path Problem

• D[k-1][i][j]와 D[k][i][j]간의 관계: (1)과 (2) 중 작은 값(짧은 경로의 길이)이 D[k][i][j]가 됨

​

​

• 모든 k, i, j에 대해 위의 재귀 관계식을 계산하면 전쌍 최단 경로의 길이를 구할 수 있음
• 하지만, D[k][i][j]의 계산에는 D[k-1][i][j]만이 사용되므로, n x n x n 크기의 3차원 배열 대신 n x n 크기의 2차원 배열로 구현할 수 있음

​

27

D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j])

D[i][j] = min(D[i][j], D[i][k] + D[k][j])

플로이드Floyd의 알고리즘: 구현

최단 경로 문제Shortest Path Problem

28

1 def floyd(W, n):

2 D = [[0 for _ in range(n)] for _ in range(n)]

3 P = [[-1 for _ in range(n)] for _ in range(n)]

4

5 for i in range(n):

6 for j in range(n):

7 D[i][j] = W[i][j]

8

9 for k in range(n):

10 for i in range(n):

11 for j in range(n):

12 if D[i][k] + D[k][j] < D[i][j]:

13 D[i][j] = D[i][k] + D[k][j]

14 P[i][j] = k

15 return D, P

1 def path_reconstruction(P, i, j, path):

2 if P[i][j] == -1:

3 path.append(u)

4 return

5 path_reconstruction(P, i, P[i][j], path)

6 path_reconstruction(P, P[i][j], j, path)

플로이드Floyd의 알고리즘: 최단 경로 출력

최단 경로 문제Shortest Path Problem

• 최단 경로 v_i → v_j 사이에 들려야 하는 중간 정점 v_k들을 P[i][j]에 기록함
• 최단 경로 v_i → v_j는 P[i][j]에 저장된 중간 정점 v_k를 거치는 경로 v_i → v_k → v_j
• 최단 경로 v_i → v_k 는 P[i][k]에 저장된 중간 정점 v_{k`</sub>를 거치는 경로 v<sub>i</sub> → v<sub>k`} → v_k 이며, 최단 경로 v_k → v_j는 P[k][j]에 저장된 중간 정점 v_{k``</sub>를 거치는 경로 v<sub>k</sub> → v<sub>k``} → v_j
• 최단 경로 v_i → v<sub>k`</sub> 는 P[i][k`]에 저장된…

​

29

1 def floyd(W, n):

2 D = [[0 for _ in range(n)] for _ in range(n)]

3 P = [[-1 for _ in range(n)] for _ in range(n)]

4

5 for i in range(n):

6 for j in range(n):

7 D[i][j] = W[i][j]

8

9 for k in range(n):

10 for i in range(n):

11 for j in range(n):

12 if D[i][k] + D[k][j] < D[i][j]:

13 D[i][j] = D[i][k] + D[k][j]

14 P[i][j] = k

15 return D, P

1 def path_reconstruction(P, i, j, path):

2 if P[i][j] == -1:

3 path.append(u)

4 return

5 path_reconstruction(P, i, P[i][j], path)

6 path_reconstruction(P, P[i][j], j, path)

단일 도착점 최단 경로 문제를 푸는 대표적 알고리즘?

최단 경로 문제Shortest Path Problem

• 도착점을 출발점으로, 간선의 방향을 반대로 한 단일 출발점 최단 경로 문제를 푸는 알고리즘을 이용

30

문제: 소방서Fire Station

31

설명

문제: 소방서Fire Station

• 가장 먼 곳에 있는 집으로부터 거리를 최소화 할 수 있는 위치에 새로운 소방서를 지어라
• 도시에는 최대 500개의 교차로가 있으며, 각 교차로는 번호로 구분
• 각 교차로는 양방향 도로로 연결되며, 한 교차로에 연결된 도로는 20개 미만
• 한 교차로에서 다른 교차로로 갈 수 있는 경로가 항상 존재
• 모든 교차로에는 적어도 하나의 집이 존재
• 일부 교차로에는 이미 지어진 최대 100개의 소방서가 있으며, 이 때 한 교차로에 하나 이상의 소방서가 존재할 수 있음
• 가장 먼 곳에 있는 집으로부터 소방서 간의 거리를 최소화 할 수 있는 새로운 소방서 위치(즉, 교차로 번호) 중 가장 작은 값을 출력

32

예시

문제: 소방서Fire Station

입력

​

출력

​

33

2

​

1 6

2

1 2 10

2 3 10

3 4 10

4 5 10

5 6 10

6 1 10

​

1 6

2

1 2 10

2 3 10

3 4 10

4 5 10

5 6 10

6 1 10

5

​

5

테스트 케이스 개수

소방서의 개수, 교차로의 개수

새 소방서의 교차로 번호

소방서가 위치한 교차로 번호

한 교차로 번호,

다른 교차로 번호,

도로의 길이

다음 테스트 케이스

다음 테스트케이스의 답

힌트

문제: 소방서Fire Station

• 교차로를 정점, 도로를 간선, 거리를 가중치로 하는 그래프를 구축
• 각 교차로에서 다른 교차로로 가는 전쌍 최단 경로를 구함
• 임의의 한 교차로에 소방서를 지은 후에, 다른 모든 교차로(즉, 집)에서 가장 가까운 소방서까지의 거리를 찾음(최단 경로)
• 이 최단 경로 중에서 가장 긴 경로가 소방서에서 가장 멀리 있는 집의 거리이며, 이를 최소화하는 것이 목적
• 모든 교차로에 소방서를 지어보면서 소방서에서 가장 멀리 있는 집의 거리가 최소화되는 교차로를 찾으면 됨

34

문제: 황혼에서 새벽까지

From Dusk Till Dawn

35

설명

문제: 황혼에서 새벽까지From Dusk Till Dawn

• 뱀파이어인 블라디미르가 최소한의 피만 챙겨서 한 도시에서 다른 도시로 열차 여행을 할 수 있는 여행 경로를 찾아라
• 도시의 개수는 최대 100개임
• 열차 노선은 출발 도시, 도착 도시, 출발 시간, 소요 시간으로 구성되며, 최대 1,000개임
• 출발 시간은 24시간 표기로 주어지며, 항상 정각에 출발함(예. 19: 19시 출발)
• 소요 시간은 시Hour 단위의 정수로 주어짐(예. 3: 3시간)
• 노선은 양방향이 아님

36

설명

문제: 황혼에서 새벽까지From Dusk Till Dawn

• 뱀파이어인 블라디미르가 최소한의 피만 챙겨서 한 도시에서 다른 도시로 열차 여행을 할 수 있는 여행 경로를 찾아라
• 블라디미르는 뱀파이어이기 때문에, 황혼에서 새벽까지(오후 6시부터 오전 6시)까지만 여행할 수 있음
• 오후 6시 전에 출발할 수도 없고, 오전 6시 이후에 도착할 수도 없음
• 만약, 오전 6시에 한 도시에 도착한다면 블라디미르는 열차역의 음습한 곳에 관을 두고 오후 6시까지 휴식을 취함
• 블라디미르는 뱀파이어이기 때문에, 낮 12시에 관 안에서 1리터씩 피를 마심
• 블라디미르가 여행을 위해 준비해야 하는 최소 용량의 피의 양을 구해야 함

37

예시

문제: 황혼에서 새벽까지From Dusk Till Dawn

입력

​

출력

​

38

2

3

Ulm Muenchen 17 2

Ulm Muenchen 19 12

Ulm Muenchen 5 2

Ulm Muenchen

10

Lugoj Sibiu 12 6

Lugoj Sibiu 18 6

Lugoj Sibiu 24 5

Lugoj Medias 22 8

Lugoj Medias 18 8

Lugoj Reghin 17 4

Sibiu Reghin 19 9

Sibiu Medias 20 3

Reghin Medias 20 3

Reghin Bacau 24 6

Lugoj Bacau

Test Case 1.

There is no route Vladimir can take.

Test Case 2.

Vladimir needs 2 litre(s) of blood.

테스트케이스 개수

열차 노선의 개수

열차 노선

(출발 도시, 도착 도시, 출발 시각, 소요 시간)

출발 도시와 목적 도시

다음 테스트케이스

여행 경로가 존재할 시 필요한 최소한의 피

테스트케이스 번호

여행 경로가 없을 시

힌트

문제: 황혼에서 새벽까지From Dusk Till Dawn

• 도시를 정점, 한 도시에서 다른 도시로 가는 노선을 방향이 있는 간선, 소요 시간을 가중치로 하는 그래프를 구축
• 출발 도시에서 도착 도시로 가는 최단 경로의 길이를 구하면 됨
• 쉬워 보이지만 세 가지를 고려해야 함
• 블라디미르가 여행할 수 있는 노선(오후 6시 ~ 오전 6시 사이)인지 확인
• 최초 출발 시각과 총 여행 시간으로 현재 시각을 구해서 탈 수 있는 노선을 확인
• 노선의 소요 시간만을 고려할 게 아니라, 노선의 출발 시각을 고려해서 여행 시간을 산출
• 예. 도시 A에 20시에 도착하였고, 도시 A에서 도시 B로 가는 노선은 23시에 출발하여 2시간이 걸린다고 하면, 도시 A에서 B로 가는 총 소요 시간은 3시간(대기 시간) + 2시간(여행 시간) = 5시간

39

문제: 티모의 여행Teemo’s Trip

40

설명

문제: 티모의 여행Teemo’s Trip

• 티모가 바다로 여행을 가기 위해 지불해야 하는 최소의 도로 사용료를 계산하라
• 올해 농사를 성공적으로 마친 티모는 즐거운 마음으로 바다 여행을 가려고 함
• 티모는 1번 도시에서 출발하여, 바다가 있는 N번 도시에 도착하려고 함(1 ≤ N ≤ 10,000)
• 도시들은 총 M개의 양방향 도로로 연결되어 있으며 (1 ≤ M ≤ 50,000), 도로를 이용할 때마다 도로 사용료 P를 내야함(0 ≤ P ≤ 1,000,000)

41

설명

문제: 티모의 여행Teemo’s Trip

• 티모가 바다로 여행을 가기 위해 지불해야 하는 최소의 도로 사용료를 계산하라
• 단, 티모는 돈을 조금이라도 아끼기 위해서 도로 요금을 직접 재배한 버섯으로 지불하려고 함
• 도로 요금이 얼마든지 간에, 버섯 하나를 내면 해당 도로는 영원히 무료로 이용할 수 있음
• 티모는 최소 1개, 최대 20개의 버섯을 가지고 있음

42

예시

문제: 티모의 여행Teemo’s Trip

입력

​

출력

​

43

10 20 3

1 3 50

1 8 3

1 10 15

2 10 37

2 9 42

2 9 14

2 3 44

2 8 26

3 6 80

3 6 60

3 7 12

3 9 66

3 4 81

4 8 6

5 10 45

5 6 73

6 7 83

6 7 83

7 10 14

8 10 59

0

도시의 수, 도로의 수, 버섯의 수

바다가 있는 도시로 가기 위해 필요한 최소 비용

i번째 도시와 j번째 도시를 연결하는 도로의 비용

힌트

문제: 티모의 여행Teemo’s Trip

• 도시는 정점, 양방향 도로는 간선, 도로 사용료는 가중치인 그래프를 구축
• 문제는 버섯의 존재인데, 티모의 벼농사처럼 새로운 정점을 만들어서 한 정점에서 다른 정점으로 가는 가중치가 없는 간선을 생성함
• 각 정점에 대해서 버섯의 개수만큼 새로운 정점이 생길 수 있음
• 즉, 도시 개수 × (버섯의 개수 + 1)만큼의 정점을 생성하며, 생성된 정점을 (도시 번호, 남은 버섯의 개수)로 생각하면 됨
• 예. (1, 3)은 도시 번호 1에서 버섯이 3개 남은 정점을 의미

44

힌트

문제: 티모의 여행Teemo’s Trip

• 남은 버섯의 개수가 m개일 때, 한 도시 A에서 다른 도시 B로 이동하는 비용 및 경우는 두 가지:
• m개의 버섯이 남은 채 A까지 이동한 최소 비용을 D[(A, m)]이라고 할 때,
• 경우 1: 도시 A에서 B로 도로 사용료를 내고 이동
• 총 비용: D[(A, m)] + (A, B)를 연결하는 간선의 가중치
• 도착 정점: (B, m)
• 경우 2: 도시 A에서 B로 도로 사용로 대신 버섯을 내고 이동
• 총 비용: D[(A, m)]
• 도착 정점: (B, m - 1)
• 이러한 규칙을 고려해서 도시 이동 및 최단 경로를 찾아야 함

45