๋ฌธ์
https://www.acmicpc.net/problem/1368
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x1B๊ฐ - ์ต์ ์ ์ฅ ํธ๋ฆฌ
์๊ณ ๋ฆฌ์ฆ: ์ต์ ์คํจ๋ ํธ๋ฆฌ
ํ์ด

์ด๋ค ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋๋์ ๋ฐ๋ผ ํ์ด ๋ฐฉ์์ด ๋ฌ๋ผ์ง๋ค.
1๏ธโฃ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ ์ฌ์ฉ
ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ๊ธฐ๋ณธ์ ์ผ๋ก (๋
ธ๋1, ๋
ธ๋2, ๋น์ฉ)ํํ์ ๋ฐ์ดํฐ๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ์ฌ ์ฌ์ฉํ๋ค.
ํ์ง๋ง ์ด ๋ฌธ์ ์์๋ ๋ ๊ฐ์ง ์กฐ๊ฑด์ด ์ ์๋๋ค.
1) ๋ค๋ฅธ ๋ ผ์์ ๋ฌผ์ ๋์ด์ฌ๊ฒ์ธ์ง
2) ๋ ผ์ ์๋ก์ด ์ฐ๋ฌผ์ ํ ๊ฒ์ธ์ง
→ ์ผ๋จ ์ ๋ ฌ ํ ์ฐ๊ฒฐ๋น์ฉ๊ณผ ์ฐ๋ฌผ๋น์ฉ ์ค์์ ๋น๊ตํด์ผํ๋? ์ถ์์ง๋ง ์๋์๋ค.
๐๏ธ ๊ฐ์์ ๋
ผ N์ ์ค์ ํ ๋ค, (i, N, ๋
ผ i์ ์ฐ๋ฌผ๋น์ฉ)์ ๊ทธ๋ํ์ ์ถ๊ฐ๋ก ์ ์ฅํด์ฃผ๋ฉด ๋๋ค.
๊ทธ๋ผ ๋ชจ๋ ๋
ผ๊ณผ ๊ฐ์์ ๋
ผ ์ฌ์ด์ ์ฐ๋ฌผ์ ํ๋ ๋น์ฉ์ผ๋ก ๊ฐ์ ์ด ์ฐ๊ฒฐ๋๊ณ , ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํ ์ ์๋ค.
- ๋ง์ฝ ๋
ผ i์ ์ง์ ์ฐ๋ฌผ์ ํ๋๊ฒ์ด ๋ ์ ๋ ดํ๋ค๋ฉด,
(i, N)๊ฐ์ ์ด ์ ํ๋จ - ๋ค๋ฅธ ๋
ผ j๋ก๋ถํฐ ๋ฌผ์ ๋์ด์ค๋๊ฒ์ด ๋ ์ ๋ ดํ๋ค๋ฉด,
(i, j)๊ฐ์ ์ด ์ ํ๋จ
์ด๋ฐ์์ผ๋ก ์์ฐ์ค๋ฝ๊ฒ 1) ๋ฌผ์ ๋์ด์ค๋๋น์ฉ, 2) ์ฐ๋ฌผ์ ํ๋ ๋น์ฉ ์ค ๋ ์์ ๊ฐ์ ์ ํํ ์ ์๋ค.
N์ ๋ํ ์ถ๊ฐ ๊ฐ์ ์ด์ธ์๋ ๊ธฐ์กด ํฌ๋ฃจ์ค์นผ ๋ก์ง๊ณผ ๋์ผํ๋ค.
์ ์ฒด ์ฝ๋
# 1. ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ ํ์ด
# ๋ฉ๋ชจ๋ฆฌ: 38240KB / ์๊ฐ: 88ms
from sys import stdin
input = stdin.readline
N = int(input())
water = [int(input()) for _ in range(N)]
# ๊ฐ์์ ๋
ผ N์ ์ค์ ํด์ผํ ๋ฏ.
# (i, N) => i๋ฒ์งธ ๋
ผ์์ ์ง์ ์ฐ๋ฌผ์ ํ๋ ๊ฒฝ์ฐ
graph = [(i, N, water[i]) for i in range(N)]
for i in range(N):
line = list(map(int, input().split()))
for j in range(i):
graph.append((i, j, line[j]))
parent = list(range(N+1))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
a, b = find(a), find(b)
if a != b:
if a < b:
parent[b] = a
else:
parent[a] = b
return True
return False
ret = 0
graph.sort(key=lambda x: x[2])
for u, v, w in graph:
if union(u, v):
ret += w
print(ret)
2๏ธโฃ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ ํ์ด
ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ ์์์ ์ ๋ถํฐ ๋จ๊ณ์ ์ผ๋ก ํธ๋ฆฌ๋ฅผ ํ์ฅํด ๋๊ฐ๋ ๋ฐฉ์์ด๋ค.
๋ฐ๋ผ์ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ ๊ฒฝ์ฐ ์ฐ๋ฌผ๋น์ฉ์ด ๊ฐ์ฅ ์์ ๋
ผ์ ๋จผ์ ํ๋ฌ์ผํ๋ค.
๊ทธ๋ฆฌ๊ณ ํด๋น ๋
ผ์ ๊ธฐ์ค์ผ๋ก MST๋ฅผ ๊ตฌ์ฑํ๋๋ฐ, (ํ์ฌ๊น์ง์ ์ต์๋น์ฉ, ์ฐ๋ฌผ๋น์ฉ, ๋์ด์ค๋ ๋น์ฉ) ์ค ์ต์๊ฐ์ ์ ํํ๋ฉด ๋๋ค.
(๋ฆฌ์คํธ or heapq ๋ชจ๋์ ์ฌ์ฉํด์ ํ ์ ์๋ค.)
๋ฆฌ์คํธ ์ฌ์ฉ
๊ณผ์ ์ ๋ค์๊ณผ ๊ฐ๋ค.
- ๊ฐ์ฅ ์ ์ ์ฐ๋ฌผ ๋น์ฉ์ ๊ฐ์ง ๋ ผ์ ์ ํ
- ํด๋น ๋ ผ์ ์ฐ๋ฌผ ๋น์ฉ์ ์ด๊ธฐ ๋น์ฉ์ผ๋ก ์ค์
- ์ ์ฒด N๊ฐ์ ๋
ผ์ ๋ํด ๋ฐ๋ณต
- ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ๋ ผ ์ค ์ต์ ๋น์ฉ์ ๊ฐ์ง ๋ ผ์ ์ ํ
- ํด๋น ๋ ผ์ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ ํ ์ ์ฒด ๋น์ฉ์ ๋ํด์ค
- ์ ํํ ๋
ผ์์ ์ฐ๊ฒฐํ ์ ์๋ ๋ค๋ฅธ ๋
ผ๋ค์ ๋น์ฉ์ ์
๋ฐ์ดํธ
min(ํ์ฌ๊น์ง์ ํด๋น ๋ ผ ์ต์๋น์ฉ, ์ฐ๋ฌผ๋น์ฉ, ์ฐ๊ฒฐ๋น์ฉ)
์ ์ฒด ์ฝ๋
# 2. ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ ํ์ด (๋ฆฌ์คํธ)
# ๋ฉ๋ชจ๋ฆฌ: 35480KB / ์๊ฐ: 72ms
from sys import stdin
input = stdin.readline
N = int(input())
water = [int(input()) for _ in range(N)]
graph = [tuple(map(int, input().split())) for _ in range(N)]
cost = [float("inf")] * N
visited = [False] * N
# ์์์ ์ฐพ๊ธฐ (๊ฐ์ฅ ์์ ์ฐ๋ฌผ ๋น์ฉ)
start = -1
start_water = float("inf")
for i in range(N):
if water[i] < start_water:
start = i
start_water = water[i]
cost[start] = start_water
ret = 0
for _ in range(N):
min_cost = float("inf")
min_node = -1
for i in range(N):
if not visited[i] and cost[i] < min_cost:
min_cost = cost[i]
min_node = i
visited[min_node] = True
ret += min_cost
for nxt in range(N):
if visited[nxt]:
continue
# ๊ฐ๊ฐ์ ๋น์ฉ์ ๋
๋ฆฝ์ ์ผ๋ก ๋น๊ต
cost[nxt] = min(cost[nxt], graph[min_node][nxt], water[nxt])
print(ret)
์ฐ์ ์์ ํ(heapq) ์ฌ์ฉ
๋ฆฌ์คํธ ๊ตฌํ ๋ฐฉ์๊ณผ ๋์ผํ์ง๋ง, ์ต์ ๋น์ฉ์ ์ฐพ๋ ๊ณผ์ ์ ํ์ผ๋ก ์ต์ ํํ๊ฒ์ด๋ค.
๊ณผ์ ์ญ์ ๊ฑฐ์ ๋์ผํจ.
- ๊ฐ์ฅ ์ ์ ์ฐ๋ฌผ ๋น์ฉ์ ๊ฐ์ง ๋ ผ์ ์ ํ
- heap์
(๋น์ฉ, ๋ ผ ๋ฒํธ)์ฝ์ - ๋น์ฉ์ด ์ ์ ๊ฒฝ์ฐ๋ถํฐ ํ๋์ฉ ๊บผ๋ด๋ฉฐ ์ฒดํฌํจ
- ์ด๋ฏธ ๋ฐฉ๋ฌธํ ๋ ธ๋๋ผ๋ฉด ๊ฑด๋๋
- ์๋๋ผ๋ฉด ๋ฐฉ๋ฌธ์ฒ๋ฆฌ ํ ํ์์ ๊บผ๋ธ ๋น์ฉ์ ์ ์ฒด ๋น์ฉ์ ์ถ๊ฐ
- ๋
ธ๋ ์ ์นด์ดํธ +1
- ๋ง์ฝ ์นด์ดํธํ ๋ ธ๋ ์๊ฐ N ์ด์์ด๋ผ๋ฉด ์ต์ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ์์ฑํ ์ ์ด๋ฏ๋ก break
- (๋ค๋ฅธ ๋ ผ๊ณผ ์ฐ๊ฒฐํ๋ ๋น์ฉ, ์ฐ๋ฌผ์ ํ๋ ๋น์ฉ) ์ค ๋ ์์ ๊ฐ์ ์ ํ
- ํด๋น ๊ฐ์ด ํ์ฌ๊น์ง ํด๋น ๋ ผ์ ์ต์๋น์ฉ๋ณด๋ค ์๋ค๋ฉด ์ ๋ฐ์ดํธ ํ ํ์ ์ถ๊ฐ
์ ์ฒด ์ฝ๋
# 3. ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ ํ์ด (heapq)
# ๋ฉ๋ชจ๋ฆฌ: 37556KB / ์๊ฐ: 72ms
from sys import stdin
from heapq import heappush, heappop
input = stdin.readline
N = int(input())
water = [int(input()) for _ in range(N)]
graph = [tuple(map(int, input().split())) for _ in range(N)]
costs = [float("inf")] * N
visited = [False] * N
# ์์์ ์ฐพ๊ธฐ (๊ฐ์ฅ ์์ ์ฐ๋ฌผ ๋น์ฉ)
start = -1
start_water = float("inf")
for i in range(N):
if water[i] < start_water:
start = i
start_water = water[i]
heap = [(start_water, start)]
costs[start] = start_water
ret = cnt = 0
while heap:
cost, node = heappop(heap)
if visited[node]:
continue
visited[node] = True
ret += cost
cnt += 1
if cnt >= N:
break
for nxt, cost in enumerate(graph[node]):
if visited[nxt]:
continue
# ๋ค๋ฅธ ๋
ผ๊ณผ ์ฐ๊ฒฐํ๋ ๋น์ฉ, ์ฐ๋ฌผ์ ํ๋ ๋น์ฉ ์ค ๋ ์์ ๊ฐ์ ์ ํ
new_cost = min(cost, water[nxt])
# ํด๋น ๊ฐ์ด ์ต์๋น์ฉ๋ณด๋ค ์๋ค๋ฉด ์
๋ฐ์ดํธ ํ ํ์ ์ถ๊ฐํ๋ค.
if new_cost < costs[nxt]:
heappush(heap, (new_cost, nxt))
costs[nxt] = new_cost
print(ret)
๊ฐ์ธ์ ์ผ๋ก ํฌ๋ฃจ์ค์นผ์ ์ฌ์ฉํ ํ์ด๊ฐ ๋ง์์ ๋ ๋ค.
N๋ฒ์งธ ๋ ผ์ผ๋ก ์ค์ ํ๋ ์ฐธ ๊ฐ๋จํ๋ค...