
์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ
์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ์ ๋ค์๊ณผ ๊ฐ์ด ๊ฒฝ์ฐ๋ฅผ ๋๋ ์ ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ์ด ๋ค๋ฅด๋ค.
1. ๋จ์ผ ์ถ๋ฐ์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ ๊ฒฝ์ฐ
a. Dijkstra's Algorithm (๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ): ๊ฐ์ ์ ์์ ๊ฐ์ค์น๋ง ํ์ฉ
b. Bellman-Ford Algorithm (๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ): ๊ฐ์ ์ ์, ์์ ๊ฐ์ค์น ๋ชจ๋ ํ์ฉ
c. BFS : ๊ฐ์ ์ ๊ฐ์ค์น๊ฐ ์๋ ๊ฒฝ์ฐ
2. ๊ทธ๋ํ ๋ด์ ๋ชจ๋ ์ ์ ์ ๊ฐ์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ ๊ฒฝ์ฐ
a. Floyd-Warshall (ํ๋ก์ด๋-์์ ์๊ณ ๋ฆฌ์ฆ): ๊ฐ์ ์ ์, ์์ ๊ฐ์ค์น ๋ชจ๋ ํ์ฉ
b. Johnson's Algorithm (์กด์จ ์๊ณ ๋ฆฌ์ฆ): ๊ฐ์ ์ ์, ์์ ๊ฐ์ค์น ๋ชจ๋ ํ์ฉ
์ด ์ค ์ด๋ฒ์๋ ํ๋ก์ด๋-์์ ์๊ณ ๋ฆฌ์ฆ์ ๋ํด ์์๋ณด๊ณ ์ ํ๋ค.
ํ๋ก์ด๋-์์ (Floyd-Warshall) ์๊ณ ๋ฆฌ์ฆ์ด๋?
๊ทธ๋ํ ๋ด์ ๋ชจ๋ ์ ์ ์ ๊ฐ์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๋ฐ ์ฌ์ฉ๋๋ ๋์ ํ๋ก๊ทธ๋๋ฐ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ํ๋ก์ด๋-์์ ์ ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ์ง ๊ทธ๋ํ์์๋ ์๋ํ๋ฉฐ, ์์ ๊ฐ์ค์น ์ฌ์ดํด์ ๊ฐ์งํ ์ ์๋ค. ํ๋ก์ด๋-์์ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ๋ณต์ก๋๋ O(N^3)์ผ๋ก ๋ค์ต์คํธ๋ผ์ ์ธ์ ํ๋ ฌ๋ฒ์ ๊ณผ ๋์ผํ์ง๋ง, ๊ตฌํ์ด ๋งค์ฐ ๊ฐ๋จํ์ฌ ๋ค์ต์คํธ๋ผ๋ณด๋ค ํจ์จ์ ์ด๋ค. ๊ตฌํ์ด ๊ฐ๋จํ๋ค๋ ๊ฒ์ ์๋์์ ํ์ธํด๋ณด๊ฒ ๋ค.
DP ์ ๊ทผ๋ฒ
ํ๊ฐ์ ์ ์ ๋ถํฐ ์์ํด์ 1~n๊ฐ๊น์ง์ ๋ชจ๋ ์ ์ ์ ๊ฒฝ์ ๊ฐ๋ฅํ ์ ์ ์ผ๋ก ๊ณ ๋ คํ๋ฉด์, ๋ชจ๋ ์์ ์ต๋จ ๊ฒฝ๋ก์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ์ฐํ๋ค. ์์์ต์ ํด๋ฅผ ๊ตฌํ๊ณ ํ์ฌ ๊ฐ๊ณผ ๋น๊ตํ์ฌ ๊ณ์ํด์ ์ต์ ํด๋ฅผ ๊ตฌํด๋๊ฐ๋ ๋ฐฉ๋ฒ์ด๋ค.
๋ฐ๋ผ์, ๋ถ๋ถ ๋ฌธ์ ๋ ์ ์ 1~k๊ฐ๋ฅผ ๊ฒฝ์ ๊ฐ๋ฅํ ์ ์ ์ผ๋ก ๊ณ ๋ คํด์ ์ ์ i๋ถํฐ ์ ์ j๊น์ง์ ๋ชจ๋ ๊ฒฝ๋ก ์ค์์ ์ต๋จ ๊ฒฝ๋ก D[i][j]๋ฅผ ๊ตฌํ๋ ๊ฒ!
ex) i → j / i → ์ ์ 1 → j / i → ์ ์ 1 → ์ ์ 2 → j / ..... / i → ์ ์ 1 → ... → k → j ์ค์์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ ๊ฒ
์ํ ๊ณผ์

k=0
| 0 | 5 | INF | 3 | INF |
| INF | 0 | INF | INF | 4 |
| INF | INF | 0 | 1 | 2 |
| -1 | INF | INF | 0 | -1 |
| INF | -2 | 3 | 2 | 0 |
ํ์ด ์์์ , ์ด์ด ๋์ฐฉ์ ์ธ ํ ์ด๋ธ.
์ด๊ธฐ ์ํ๋ ์ ์ i์์ ์ ์ j๋ก ์ง์ ๊ฐ๋ ๊ฒฝ๋ก๊ฐ ์ต๋จ ๊ฒฝ๋ก๋ก, ๊ฐ์ค์น๋ฅผ ๋ฐ๋ก ์ ์ฅํด์ฃผ๋ฉด ๋๋ค.
k=1
| 0 | 5 | INF | 3 | INF |
| INF | 0 | INF | INF | 4 |
| INF | INF | 0 | 1 | 2 |
| -1 | 4 | INF | 0 | -1 |
| INF | -2 | 3 | 2 | 0 |
์ ์ 4 → ์ ์ 2๋ก ๋ฐ๋ก ๊ฐ๋ ๊ฒฝ๋ก๋ณด๋ค ์ ์ 1์ ๊ฑฐ์ณ ๊ฐ๋ ๊ฒฝ๋ก๊ฐ ๋ ์๊ธฐ ๋๋ฌธ์ ๊ฐฑ์
k=2
| 0 | 5 | INF | 3 | 9 |
| INF | 0 | INF | INF | 4 |
| INF | INF | 0 | 1 | 2 |
| -1 | 4 | INF | 0 | -1 |
| INF | -2 | 3 | 2 | 0 |
k=3
| 0 | 5 | INF | 3 | 9 |
| INF | 0 | INF | INF | 4 |
| INF | INF | 0 | 1 | 2 |
| -1 | 4 | INF | 0 | -1 |
| INF | -2 | 3 | 2 | 0 |
k=4
| 0 | 5 | INF | 3 | 2 |
| INF | 0 | INF | INF | 4 |
| 0 | 5 | 0 | 1 | 0 |
| -1 | 4 | INF | 0 | -1 |
| 1 | -2 | 3 | 2 | 0 |
k=5
| 0 | 0 | 5 | 3 | 2 |
| 5 | 0 | 7 | 6 | 4 |
| 0 | -2 | 0 | 1 | 0 |
| -1 | -3 | 2 | 0 | -1 |
| 1 | -2 | 3 | 2 | 0 |
์ฝ๋ (Python)
ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ์ ์ฐ๋ ๋ฌธ์ ์ค ๋ฐฑ์ค์ 11404 <ํ๋ก์ด๋> ๋ฌธ์ ์ ์ฝ๋๋ฅผ ๋ค๊ณ ์๋ค.
import sys
input = sys.stdin.readline
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
graph[i][i] = 0
for _ in range(m):
s, e, w = map(int, input().split())
graph[s][e] = min(graph[s][e], w)
# ๊ฑฐ์ณ๊ฐ๋ ๊ฒฝ๋ก ์ค ๋ ์ต๋จ๊ฒฝ๋ก๊ฐ ์์ผ๋ฉด ๊ฐฑ์
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()
๋ํ ๋ฌธ์
1389๋ฒ: ์ผ๋น ๋ฒ ์ด์ปจ์ 6๋จ๊ณ ๋ฒ์น
์ฒซ์งธ ์ค์ ์ ์ ์ ์ N (2 ≤ N ≤ 100)๊ณผ ์น๊ตฌ ๊ด๊ณ์ ์ M (1 ≤ M ≤ 5,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์๋ ์น๊ตฌ ๊ด๊ณ๊ฐ ์ฃผ์ด์ง๋ค. ์น๊ตฌ ๊ด๊ณ๋ A์ B๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, A์ B๊ฐ ์น๊ตฌ๋ผ๋ ๋ป
www.acmicpc.net
11404๋ฒ: ํ๋ก์ด๋
์ฒซ์งธ ์ค์ ๋์์ ๊ฐ์ n์ด ์ฃผ์ด์ง๊ณ ๋์งธ ์ค์๋ ๋ฒ์ค์ ๊ฐ์ m์ด ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ์ ์งธ ์ค๋ถํฐ m+2์ค๊น์ง ๋ค์๊ณผ ๊ฐ์ ๋ฒ์ค์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ๋จผ์ ์ฒ์์๋ ๊ทธ ๋ฒ์ค์ ์ถ๋ฐ ๋์์ ๋ฒํธ๊ฐ
www.acmicpc.net
1956๋ฒ: ์ด๋
์ฒซ์งธ ์ค์ V์ E๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) ๋ค์ E๊ฐ์ ์ค์๋ ๊ฐ๊ฐ ์ธ ๊ฐ์ ์ ์ a, b, c๊ฐ ์ฃผ์ด์ง๋ค. a๋ฒ ๋ง์์์ b๋ฒ ๋ง์๋ก ๊ฐ๋ ๊ฑฐ๋ฆฌ๊ฐ c์ธ ๋๋ก๊ฐ ์๋ค๋ ์
www.acmicpc.net
'๐ฅ๏ธ Study > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| [์ฝ๋ํธ๋ฆฌ ์กฐ๋ณ๊ณผ์ ] BFS ๋น๋ฅผ ํผํ๊ธฐ Python (0) | 2024.08.06 |
|---|---|
| [์ฝ๋ํธ๋ฆฌ ์กฐ๋ณ๊ณผ์ ] ์๋ฎฌ๋ ์ด์ 1์ฐจ์ ๋ฐ๋ Python (9) | 2024.07.23 |
| [Algorithm/DP] ์ต์ฅ ์ฆ๊ฐ ๋ถ๋ถ ์์ด(LIS, Longest Increasing Subsequence) (0) | 2023.09.29 |
| [Algorithm/DP] 0/1 Knapsack Problem (๋ฐฐ๋ญ ๋ฌธ์ ) (0) | 2023.09.25 |