1 of 48

문제해결 프로그래밍

최소 비용 신장 트리

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

2 of 48

강의 순서

최소 비용 신장 트리Minimum Spanning Tree
문제: 주근깨Freckles
문제: 여행자 가이드Tourist Guide
문제: 티모의 벼농사Teemo’s Rice Farming

2

3 of 48

최소 비용 신장 트리Minimum Spanning Tree

3

4 of 48

트리

최소 비용 신장 트리Minimum Spanning Tree

연결되어 있는Connected 비순환적Acyclic 비방향Undirected 그래프

연결되어 있는: 임의의 정점에서 다른 정점으로 가는 경로가 항상 존재
비순환적: 한 정점에서 두 개 이상의 다른 정점을 방문하고 같은 정점으로 가는 경로가 존재하지 않음
비방향: 간선에 방향이 존재하지 않음

4

5 of 48

트리

최소 비용 신장 트리Minimum Spanning Tree

연결되어 있는Connected 비순환적Acyclic 비방향Undirected 그래프

부모Parent 정점: 연결된 두 정점 중 시작 지점에 해당하는 정점으로, 부모 정점은 여러 개의 자식 정점을 가질 수 있음
자식Children 정점: 연결된 두 정점 중 도착 지점에 해당하는 정점으로, 뿌리 정점을 제외한 모든 자식 정점은 하나의 부모 정점을 가짐
잎Leaf 정점: 자식 정점이 없는 정점
뿌리Root 정점: 부모 정점이 없는 정점

5

6 of 48

트리

최소 비용 신장 트리Minimum Spanning Tree

연결되어 있는Connected 비순환적Acyclic 비방향Undirected 그래프

높이Height: 뿌리 정점에서 가장 먼 잎 정점까지의 거리 또는 간선의 수
깊이Depth(레벨Level): 특정 정점에서 뿌리 정점까지의 거리 또는 간선의 수
사촌Sibling 정점: 같은 깊이에 있는 정점들

6

7 of 48

최소 비용 신장 트리Minimum Spanning Tree

신장 트리: 모든 정점을 포함한 트리

즉, 모든 정점이 연결되어 있는Connected 비순환적Acyclic 비방향Undirected 그래프
그래프에는 하나 이상의 신장 트리가 있을 수 있음
정점의 수 n에 대해 신장 트리의 간선의 수는 n - 1개임

최소 비용 신장 트리: 신장 트리 중 간선의 가중치의 합이 최소인 신장 트리

그래프에는 하나 이상의 최소 비용 신장 트리가 있을 수 있음

용도

모든 도시를 연결하기 위해 건설하는 도로의 길이를 최소화(최소의 비용 소모)
모든 지역을 연결하는 광 케이블의 총 길이가 최소가 되도록 통신망을 구축
모든 가구의 하수관을 연결하는 파이프의 총 길이가 최소가 되도록 배관 설계

7

8 of 48

최소 비용 신장 트리Minimum Spanning Tree

8

9 of 48

문제 정의

최소 비용 신장 트리Minimum Spanning Tree

문제: 연결되어 있는 가중치 포함 비방향 그래프 G = (V, E)의 최소 비용 신장 트리를 구성하는 간선의 집합 F를 구하라

정점의 집합 V = {v₁, v₂, …, v_n}
간선과 가중치의 집합 E = {(v_i,1, v_j,1, w₁), (v_i,2, v_j,2, w₂), …, (v_i,n, v_j,n, w_m)}

입력: 연결되어 있는 가중치 포함 비방향 그래프 G (또는 인접 행렬 W), 정점의 개수 n, 간선의 개수 m
출력: 최소 비용 신장 트리의 간선의 집합 F

예. F = {(v_i,1, v_j,1), (v_i,2, v_j,2), …}

9

10 of 48

무차별 대입 알고리즘

최소 비용 신장 트리Minimum Spanning Tree

n - 1개의 간선을 가진 모든 부분 그래프를 찾은 후에, 그 중 순환적 경로가 없고 가중치가 최소가 되는 신장 트리를 선택

모든 정점이 다른 정점과 간선으로 연결되어 있으면 n개의 정점 중 두 정점을 선택하는 것과 같으므로 C(n, 2) = n(n - 1) / 2개의 간선이 존재
신장 트리는 간선이 n - 1개로 이루어짐
따라서, n(n - 1) / 2개의 간선들 중 n - 1개의 간선을 선택하는 방법의 수, C(n(n - 1) / 2, n - 1)가 n - 1개의 간선으로 된 부분 그래프를 탐색하는 경우의 수와 같음
이 부분 그래프들 중 순환적 경로가 없는 그래프들이 신장 트리이며, 이 중에서 최소의 가중치 합을 가진 신장 트리를 찾으면 됨

10

11 of 48

무차별 대입 알고리즘

최소 비용 신장 트리Minimum Spanning Tree

n - 1개의 간선을 가진 모든 부분 그래프를 찾은 후에, 그 중 순환적 경로가 없고 가중치가 최소가 되는 신장 트리를 선택

11

n	C(n(n - 1) / 2, n - 1)
1	1
2	1
3	3
4	20
5	210
6	3,003
7	54,264
8	1,184,040
9	30,260,340
10	886,163,135

12 of 48

프림의 알고리즘: 아이디어

최소 비용 신장 트리Minimum Spanning Tree

모든 정점의 집합 V와 신장 트리에 추가된 정점들의 집합 Y에 대해, V − Y에 속한 정점들(신장 트리에 추가되지 않은 정점) 중에서 Y에 가장 가까운 정점 하나를 선정

즉, V - Y의 정점들과 Y의 정점들을 연결하는 간선들 중 가장 작은 가중치를 가진 간선을 찾고, 해당 간선이 연결하는 V - Y의 정점을 Y에 추가

12

13 of 48

프림의 알고리즘: 의사 코드Pseudo Code

최소 비용 신장 트리Minimum Spanning Tree

13

14 of 48

프림의 알고리즘: 예

최소 비용 신장 트리Minimum Spanning Tree

14

15 of 48

프림의 알고리즘: 구현

최소 비용 신장 트리Minimum Spanning Tree

I[i]: V - Y의 정점 v_i에서 가장 가까운 Y의 정점 v_j의 인덱스 j 저장
D[i]: V - Y의 정점 v_i에서 가장 가까운 Y의 정점 v_j를 연결하는 간선의 가중치

D[i] = -1: 정점 v_i가 Y에 존재
D[i] ≥ 0: 정점 v_i가 V - Y에 존재

15

1 import sys

2

3

4 def prim(W, n):

5 F = set()

6 I = [0] * n

7 D = [0] * n

8

9 for i in range(1, n):

10 I[i] = 0

11 D[i] = W[0][i]

12

13 for k in range(n - 1):

14 d_min = sys.maxsize

15 i_min = -1

16

17 for i in range(1, n):

18 if 0 <= D[i] <= d_min:

19 d_min = D[i]

20 i_min = i

21 e = (i_min, I[i_min])

22 F.add(e)

23 D[i_min] = -1

24

25 for i in range(1, n):

26 if W[i_min][i] < D[i]:

27 D[i] = W[i_min][i]

28 I[i] = i_min

29 return F

16 of 48

프림의 알고리즘: 구현

최소 비용 신장 트리Minimum Spanning Tree

Y = {v₀}, V - Y = {v₁,v₂,v₃,v₄}
I[i]: V - Y의 정점 v_i 에서 가장 가까운 Y의 정점은 v₀이므로 인덱스 0로 초기화
D[i]: V - Y의 정점 v_i에서 가장 가까운 Y의 정점 v₀을 연결하는 가중치는 간선 (v₀, v_i)의 가중치와 같음 = W[0][i]
예.

I = [1, 1, 1, 1, 1]
D = [0, 1, 3, ∞, ∞]

16

1 import sys

2

3

4 def prim(W, n):

5 F = set()

6 I = [0] * n

7 D = [0] * n

8

9 for i in range(1, n):

10 I[i] = 0

11 D[i] = W[0][i]

12

13 for k in range(n - 1):

14 d_min = sys.maxsize

15 i_min = -1

16

17 for i in range(1, n):

18 if 0 <= D[i] <= d_min:

19 d_min = D[i]

20 i_min = i

21 e = (i_min, I[i_min])

22 F.add(e)

23 D[i_min] = -1

24

25 for i in range(1, n):

26 if W[i_min][i] < D[i]:

27 D[i] = W[i_min][i]

28 I[i] = i_min

29 return F

17 of 48

프림의 알고리즘: 구현

최소 비용 신장 트리Minimum Spanning Tree

V - Y = {v₁,v₂,v₃,v₄}에 속한 정점들 중 Y = {v₀}에 가장 가까운 정점의 인덱스 i_min를 찾음
예.

D = [0, 1, 3, ∞, ∞]에서 i_min= 1

17

1 import sys

2

3

4 def prim(W, n):

5 F = set()

6 I = [0] * n

7 D = [0] * n

8

9 for i in range(1, n):

10 I[i] = 0

11 D[i] = W[0][i]

12

13 for k in range(n - 1):

14 d_min = sys.maxsize

15 i_min = -1

16

17 for i in range(1, n):

18 if 0 <= D[i] <= d_min:

19 d_min = D[i]

20 i_min = i

21 e = (i_min, I[i_min])

22 F.add(e)

23 D[i_min] = -1

24

25 for i in range(1, n):

26 if W[i_min][i] < D[i]:

27 D[i] = W[i_min][i]

28 I[i] = i_min

29 return F

18 of 48

프림의 알고리즘: 구현

최소 비용 신장 트리Minimum Spanning Tree

Y = {v₀}에 속한 정점과 V - Y = {v₁,v₂,v₃,v₄}에 속한 정점을 잇는 간선 중 최소의 가중치를 지닌 간선 e = (i_min, I[i_min])를 F에 추가
예.

i_min= 1에서 e = (1, 0)
F = {(1, 0)}

18

1 import sys

2

3

4 def prim(W, n):

5 F = set()

6 I = [0] * n

7 D = [0] * n

8

9 for i in range(1, n):

10 I[i] = 0

11 D[i] = W[0][i]

12

13 for k in range(n - 1):

14 d_min = sys.maxsize

15 i_min = -1

16

17 for i in range(1, n):

18 if 0 <= D[i] <= d_min:

19 d_min = D[i]

20 i_min = i

21 e = (i_min, I[i_min])

22 F.add(e)

23 D[i_min] = -1

24

25 for i in range(1, n):

26 if W[i_min][i] < D[i]:

27 D[i] = W[i_min][i]

28 I[i] = i_min

29 return F

19 of 48

프림의 알고리즘: 구현

최소 비용 신장 트리Minimum Spanning Tree

D[i_min] = -1: 인덱스가 i_min인 정점을 Y에 추가
예.

D = [0, 1, 3, ∞, ∞]

↓

D = [0, -1, 3, ∞, ∞]

19

1 import sys

2

3

4 def prim(W, n):

5 F = set()

6 I = [0] * n

7 D = [0] * n

8

9 for i in range(1, n):

10 I[i] = 0

11 D[i] = W[0][i]

12

13 for k in range(n - 1):

14 d_min = sys.maxsize

15 i_min = -1

16

17 for i in range(1, n):

18 if 0 <= D[i] <= d_min:

19 d_min = D[i]

20 i_min = i

21 e = (i_min, I[i_min])

22 F.add(e)

23 D[i_min] = -1

24

25 for i in range(1, n):

26 if W[i_min][i] < D[i]:

27 D[i] = W[i_min][i]

28 I[i] = i_min

29 return F

20 of 48

프림의 알고리즘: 구현

최소 비용 신장 트리Minimum Spanning Tree

Y에 새로 추가된 인덱스가 i_min인 정점과 V - Y의 정점들을 연결하는 간선의 가중치 W[i_min][i]가 현재 알고있는 최소의 가중치 D[i]보다 작다면, D[i]를 W[i_min][i]로 갱신하고, V - Y에 가장 가까운 정점 또한 i_min로 갱신 (I[i] = i_min)

20

1 import sys

2

3

4 def prim(W, n):

5 F = set()

6 I = [0] * n

7 D = [0] * n

8

9 for i in range(1, n):

10 I[i] = 0

11 D[i] = W[0][i]

12

13 for k in range(n - 1):

14 d_min = sys.maxsize

15 i_min = -1

16

17 for i in range(1, n):

18 if 0 <= D[i] <= d_min:

19 d_min = D[i]

20 i_min = i

21 e = (i_min, I[i_min])

22 F.add(e)

23 D[i_min] = -1

24

25 for i in range(1, n):

26 if W[i_min][i] < D[i]:

27 D[i] = W[i_min][i]

28 I[i] = i_min

29 return F

21 of 48

프림의 알고리즘: 구현

최소 비용 신장 트리Minimum Spanning Tree

예.

W[i_min= 1] = [1, 0, 3, 6, ∞]
D = [0, -1, 3, ∞, ∞]
I = [1, 1, 1, 1, 1]

↓

D = [0, -1, 3, 6, ∞]
I = [1, 1, 1, 2, 1]

21

1 import sys

2

3

4 def prim(W, n):

5 F = set()

6 I = [0] * n

7 D = [0] * n

8

9 for i in range(1, n):

10 I[i] = 0

11 D[i] = W[0][i]

12

13 for k in range(n - 1):

14 d_min = sys.maxsize

15 i_min = -1

16

17 for i in range(1, n):

18 if 0 <= D[i] <= d_min:

19 d_min = D[i]

20 i_min = i

21 e = (i_min, I[i_min])

22 F.add(e)

23 D[i_min] = -1

24

25 for i in range(1, n):

26 if W[i_min][i] < D[i]:

27 D[i] = W[i_min][i]

28 I[i] = i_min

29 return F

22 of 48

크루스칼의 알고리즘: 아이디어

최소 비용 신장 트리Minimum Spanning Tree

모든 정점의 집합 V에서 정점 하나로 구성된 서로소 집합Disjoint Set을 구축

서로소 집합: A ∩ B = ∅

모든 간선들 중에서 가중치가 가장 작은 간선부터 차례대로 선택하면서, 해당 간선이 서로소인 두 부분 집합 내의 정점을 연결한다면 해당 간선을 F에 추가하고, 서로소인 두 부분 집합을 합침

22

23 of 48

크루스칼의 알고리즘: 의사 코드Pseudo Code

최소 비용 신장 트리Minimum Spanning Tree

23

24 of 48

크루스칼의 알고리즘: 예

최소 비용 신장 트리Minimum Spanning Tree

24

25 of 48

크루스칼의 알고리즘: 최소 가중치 간선 선택

최소 비용 신장 트리Minimum Spanning Tree

최소 힙Minimum Heap 사용
간선들을 가중치를 기준으로 오름차순으로 정렬한 후 차례대로 선택

25

26 of 48

크루스칼의 알고리즘: 서로소 집합 연산

최소 비용 신장 트리Minimum Spanning Tree

정점 하나만을 갖는 서로소 집합 생성: MAKE-SET
주어진 정점을 원소로 가진 서로소 집합 검색: FIND
서로소 집합을 하나의 집합으로 합치기: UNION

26

27 of 48

크루스칼의 알고리즘: 서로소 집합 연산

최소 비용 신장 트리Minimum Spanning Tree

서로소 집합 연산을 구현하는 방법은 여러 가지가 있으나, 대표적으로 트리 구조를 사용함

각 서로소 집합은 다른 트리로 구성
서로소 집합의 인덱스는 뿌리 정점의 인덱스

27

28 of 48

크루스칼의 알고리즘: 서로소 집합 연산

최소 비용 신장 트리Minimum Spanning Tree

자료구조

배열 D: D[i]의 값은 v_i의 부모 정점의 인덱스
배열 R: R[i]의 값은 v_i를 뿌리 정점으로 가지는 트리의 높이(랭크Rank)

구현 방법

MAKE-SET(v_i): 각 정점이 자신을 뿌리 정점으로 하는 트리 형성
FIND(v_i): 주어진 정점의 부모 정점(D[i])으로 반복하여 올라가서 뿌리 정점을 검색
UNION(u, v): u와 깊이 R[u]와 v의 깊이 R[v]를 비교하여 낮은 높이를 가진 트리의 뿌리 정점을 높은 높이를 가진 트리의 뿌리 정점의 자식 정점으로 연결

같은 높이일 시, 트리 u의 뿌리 정점의 자식 정점으로 트리 v의 뿌리 정점을 연결하고, u의 높이를 하나 증가(R[u] = R[u] + 1)

28

29 of 48

크루스칼의 알고리즘: 서로소 집합 연산의 예

최소 비용 신장 트리Minimum Spanning Tree

29

30 of 48

크루스칼의 알고리즘: 서로소 집합 연산의 구현

최소 비용 신장 트리Minimum Spanning Tree

30

1 def make_set(D, R, i):

2 D[i] = i

3 R[i] = 0

4

5

6 def find(D, i):

7 while D[i] != i:

8 i = D[i]

9 return i

10

11

12 def union(D, R, u, v):

13 if u == v:

14 return

15 if R[u] > R[v]:

16 D[v] = u

17 elif R[u] < R[v]:

18 D[u] = v

19 else:

20 D[v] = u

21 R[u] = R[u] + 1

31 of 48

크루스칼의 알고리즘: 최종 구현

최소 비용 신장 트리Minimum Spanning Tree

31

1 import sys

2 import heapq

3

4 def kruskal(W, n):

5 F, D, R, E = set(), [0] * n, [0] * n, dict()

6

7 for i in range(n):

8 for j in range(n):

9 e1, e2, w = (i, j), (j, i), W[i][j]

10 if e1 not in E and e2 not in E and w != sys.maxsize and i != j:

11 E[e1] = w

12

13 E = [(v, k) for k, v in E.items()]

14 heapq.heapify(E)

15 m = len(E)

16

17 for i in range(n):

18 make_set(D, R, i)

19

20 for _ in range(m):

21 _, (i, j) = heapq.heappop(E)

22 u, v = find(D, i), find(D, j)

23 if u != v:

24 union(D, R, u, v)

25 F.add((i + 1, j + 1))

26 if len(F) == n - 1:

27 break

28 return F

32 of 48

프림 알고리즘과 크루스칼 알고리즘의 성능 비교

최소 비용 신장 트리Minimum Spanning Tree

32

알고리즘	시간복잡도	간선이 적은 경우 Sparse Graph (m ≓ n)	간선이 많은 경우 Dense Graph (m ≓ n²)
프림의 알고리즘	θ(n²)	θ(n²)	θ(n²)
크루스칼의 알고리즘	θ(m log m) + θ(m log n)	θ(n log n)	θ(n² log n)

33 of 48

프림의 알고리즘의 개선 방법

최소 비용 신장 트리Minimum Spanning Tree

최소의 가중치를 갖는 간선을 찾을 때 다른 자료 구조를 활용하면 속도를 더욱 개선할 수 있음

예. 간선의 가중치를 키Key로 하는 힙을 만들고, 힙 연산을 통해 선택한 최소의 가중치를 갖는 간선 (v_i, v_j)에서 v_j가 아직 Y에 포함되지 않았으면 이 간선을 F에 추가

33

자료구조	시간복잡도	간선이 적은 경우 Sparse Graph (m ≓ n)	간선이 많은 경우 Dense Graph (m ≓ n²)
배열	θ(n²)	θ(n²)	θ(n²)
힙 Heap	θ(m log n)	θ(n log n)	θ(n²log n)

34 of 48

크루스칼의 알고리즘의 개선 방법

최소 비용 신장 트리Minimum Spanning Tree

서로소 집합 연산 중 FIND에 경로 압축Path Compression 기법을 활용하면 속도 개선이 가능

경로 압축: FIND 연산 중 만나는 모든 정점의 부모를 뿌리 정점으로 변경

34

1 def find_path_compression(D, i):

2 if D[i] != i:

3 D[i] = find_path_compression(D, D[i])

4 return D[i]

35 of 48

문제: 주근깨Freckles

35

36 of 48

설명

문제: 주근깨Freckles

36

37 of 48

설명

문제: 주근깨Freckles

등에 있는 모든 주근깨를 최소한의 잉크를 써서 연결하라

딕의 등에는 주근깨가 꽤 있으며, 이 주근깨의 위치는 실수형의 x, y 좌표로 주어짐
딕의 아들 리치는 이 주근깨들 사이에 선을 그려서 모든 주근깨를 연결하려고 함
잉크는 선의 길이만큼 소모가 됨

예. (1.0, 1.0)에 있는 주근깨와 (2.0, 2.0)에 있는 주근깨를 연결하면 (≒ 1.41)만큼의 잉크가 소모

37

38 of 48

예시

문제: 주근깨Freckles

입력

출력

38

1

3

1.0 1.0

2.0 2.0

2.0 4.0

3.41

테스트 케이스 개수

주근깨의 개수

잉크의 소모량 (소수점 둘째자리)

주근깨의 x, y 좌표

39 of 48

힌트

문제: 주근깨Freckles

각 주근깨들을 정점으로 하고, 각 주근깨와 다른 모든 주근깨 사이에 방향이 없는 간선이 존재하며, 간선의 가중치는 두 주근깨 간의 거리인 그래프를 구축

간선의 개수는 n(n-1)/2가 됨

이 그래프에서 최소 비용 신장 트리를 찾으면 됨

39

40 of 48

문제: 여행자 가이드Tourist Guide

40

41 of 48

설명

문제: 여행자 가이드Tourist Guide

도시 지도가 주어졌을 때 단속 카메라가 있는 위치를 알아내라

도시 내 N개의 지역(3 ≤ N ≤ 100)과 지역을 연결하는 양방향 도로가 있으며, 단속 카메라는 임의의 한 지역에서 출발하여 다른 지역으로 가기 위해 반드시 들려야 하는 곳에 설치되어 있음

41

42 of 48

예시

문제: 여행자 가이드Tourist Guide

입력

출력

42

6

sugarloaf

maracana

copacabana

ipanema

corcovado

lapa

7

ipanema copacabana

copacabana sugarloaf

ipanema sugarloaf

maracana lapa

sugarloaf maracana

corcovado sugarloaf

lapa corcovado

5

guanabarabay

…

City map #1: 1 camera(s) found

sugarloaf

City map #2: 2 camera(s) found

sambodromo

guanabarabay

지역의 개수 N

지역의 이름

도로의 개수

도로의 연결 정보

다음 테스트케이스

첫번째 테스트케이스의 카메라 대수

카메라가 설치된 지역

여러 지역에 카메라가 설치 시

매 줄마다 지역을 출력

43 of 48

힌트

문제: 여행자 가이드Tourist Guide

카메라가 있는 지역은 한 지역에서 다른 지역으로 갈 때 반드시 들려야하는 지역임
즉, 해당 지역이 사라지면 한 지역에서 다른 지역으로 갈 수가 없음
지역을 정점으로 하고, 도로를 간선으로 한 그래프를 구성
각 지역을 제거한 후 그래프 순회를 했을 때 남은 지역들 전체를 방문할 수 없다면 해당 지역에 단속 카메라가 있는 것

43

44 of 48

문제: 티모의 벼농사Teemo’s Rice Farming

44

45 of 48

설명

문제: 티모의 벼농사Teemo’s Rice Farming

티모가 운영하는 논에 물을 공급하기 위한 장비들의 최소 비용을 구하라

버섯 농장 이외에도 티모는 N개의 논(1 ≤ N ≤ 300)을 소유하고 있음
벼농사를 짓기 위해서는 이 논에 물을 공급해야 하며, 두 가지 방법이 있음

논에 직접 자동 급수 장치를 설치
물이 공급되고 있는 다른 논과 파이프로 연결

물이 공급되고 있는 논의 예

자동 급수 장치가 설치된 논 A, 논 A와 파이프로 연결된 논 B, 논 B와 파이프로 연결된 논 C 모두 물이 공급됨

45

46 of 48

설명

문제: 티모의 벼농사Teemo’s Rice Farming

티모가 운영하는 논에 물을 공급하기 위한 장비들의 최소 비용을 구하라

논마다 자동 급수 장치를 설치하는 비용은 다르며, i번째 논에 논에 자동 급수 장치를 설치하는 비용 W_i(1 ≤ W_i ≤100,000)로 주어짐
논과 논을 연결하는 파이프를 설치하는 비용 또한 서로 다르며, i번째 논과 j번째 논을 연결하는 파이프의 비용 P_i,j(1 ≤ P_i,j ≤100,000)로 주어짐

46

47 of 48

예시

문제: 티모의 벼농사Teemo’s Rice Farming

입력

출력

47

10

537

914

269

536

882

245

172

615

367

688

0 56 91 16 53 82 30 52 51 51

56 0 36 24 12 41 67 50 37 99

91 36 0 96 6 34 2 60 74 58

16 24 96 0 25 27 8 79 34 14

53 12 6 25 0 12 23 30 44 7

82 41 34 27 12 0 79 68 87 66

30 67 2 8 23 79 0 39 32 14

52 50 60 79 30 68 39 0 57 38

51 37 74 34 44 87 32 57 0 1

51 99 58 14 7 66 14 38 1 0

266

논의 개수 N

자동 급수 장치를 설치하는 비용 W_i

모든 논에 물을 공급하는 최소 비용

i번째 논과 j번째 논 사이에 파이프를 설치하는 비용 P_i,j

48 of 48

힌트

문제: 티모의 벼농사Teemo’s Rice Farming

논은 정점, 파이프는 간선, 파이프의 설치 비용 P_i,j은 간선의 가중치인 그래프를 구축할 수 있음
문제는 자동 급수 장치인데, 자동 급수 장치 또한 정점으로 생각하면 됨
자동 급수 장치에 해당하는 정점 하나를 생성하고, 이 정점과 i번째 논을 연결하는 간선의 가중치를 자동 급수 장치의 비용 W_i으로 하는 그래프를 구축
이 그래프에 대해 최소 비용 신장 트리를 찾으면 됨

48