์ธ์ ํ๋ ฌ
ํ๊ธฐ๋ฒ์ ์ฌ์ฉํ๋ค.๐๐ปํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ด๋ค ์๊ณ ๋ฆฌ์ฆ์ผ๊น?
- ์ฐ์ ๋ค์๊ณผ ๊ฐ์ ๊ทธ๋ํ๊ฐ ์๋ค๊ณ ํด๋ณด์!
- ์ด ๊ทธ๋ํ๋ฅผ
์ธ์ ํ๋ ฌ
๋ก ๋ํ๋ด๋ฉด ์๋์ ๊ฐ๋ค.
- ์ฐ๋ฆฌ๊ฐ ๊ถ๊ธํ ๊ฒ์ ๋ชจ๋ ์ ์ ์ฌ์ด์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ก, ์ฆ i๋ฒ ์ ์ ์์ j๋ฒ ์ ์ ์ฌ์ด์ ์ต๋จ๊ฑฐ๋ฆฌ์ด๋ค. (์ฌ๊ธฐ์ i, j๋ 1~4 ์ฌ์ด์ ์์์ ์ซ์์ด๋ค.)
- ๋ฐ๋ผ์, ๋ฏธ๋ฆฌ ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํ ์ต์ข ๊ฒฐ๊ณผ ๊ทธ๋ํ๋ฅผ ์ดํด๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
- ์์ ํ๋ ฌ์ ํด์ํ๋ ๋ฐฉ๋ฒ์ ํ์ด i, ์ด์ด j์ผ๋
i๋ฒ ์ ์ ์์ j๋ฒ ์ ์ ์ฌ์ด์ ์ต๋จ๊ฑฐ๋ฆฌ
์์ ๊ธฐ์ตํ๋ฉด ๋๋ค.- ์๋ฅผ ๋ค์ด์
i=1, j=3
์ผ๋ ํ๋ ฌ์ ๊ฐ์ ์ฝ์ผ๋ฉด-2
์ด๋ค.
์ด๋i๋ฒ ์ ์ ์์ j๋ฒ ์ ์ ์ฌ์ด์ ์ต๋จ๊ฑฐ๋ฆฌ๋ -2
๋ผ๊ณ ํด์ํ๋ฉด ๋๋ค.
ํต์ฌ โ adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
i์์ j์ฌ์ด์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ค๋ฉด 2๊ฐ์ง ๊ฒฝ์ฐ๋ฅผ ๋น๊ตํด์ผ ๋๋ค. k๋ฅผ ๊ฒฝ์ ์ง(์์์ ์ ์ )๋ผ๊ณ ํ์.
1) ๊ฒฝ์ ์ง k๋ฅผ ์ง๋์ง ์๋ ๊ฒฝ๋ก (i โ j
)
2) ๊ฒฝ์ ์ง k๋ฅผ ์ง๋๋ ๊ฒฝ๋ก (i โ k โ j
)
๋ฐ๋ผ์ ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ์ ์์์ (๊ฒฝ์ ์ง) ์ ์ k์ ๋ํด์ k๋ฅผ ์ง๋๋ ๊ฒฝ๋ก
vs k๋ฅผ ์ง๋์ง ์๋ ๊ฒฝ๋ก
์ค์์ ๋ ์์ ๊ฐ์ ์ต๋จ ๊ฒฝ๋ก๋ก ์ ํํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
๋ ๊ผญ์ง์ ๊ฐ์ ์ถ์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ต์ ์ด ๋ ๋๊น์ง ์ ์ง์ ์ผ๋ก ๊ฐ์ ์์ผ์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ์ฐพ๋๋ค.
โ ์ธ์ ํ๋ ฌ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ
- ์๊ธฐ์์ ์ผ๋ก ๊ฐ๋ ๊ฐ์ (i, i)์ ๊ฐ์ค์น๋ 0์ผ๋ก ์ด๊ธฐํํ๋ค.
- ์์ง ๊ฒฝ๋ก๊ฐ ์ง์ ๋์ง ์์ ๊ฐ์ ์ฌ์ด์ ๊ฑฐ๋ฆฌ๋ ๋ฌดํ๋(โ)๋ก ์ด๊ธฐํํ๋ค.
๊ฒฝ์ ์งk๋ฅผ ์ง๋๋ ์ต๋จ ๊ฒฝ๋ก
vs ๊ฒฝ์ ์ง k๋ฅผ ์ง๋์ง ์์ ๋์ ์ต๋จ ๊ฒฝ๋ก
๋ฅผ ๋น๊ตํด๋๊ฐ์.
- k = 1 / ๊ฒฝ์ ์ง๊ฐ <1>์ธ ๊ฒฝ์ฐ
1 -> 1
vs1 -> <1> -> 1
1 -> 2
vs1 -> <1> -> 2
... (์๋ต)2 -> 3
vs2 -> <1> -> 3
โญ๊ฒฝ์ ์ง๋ฅผ ์ง๋ ๋๊ฐ ๋ ์ต์๊ฐ์ด๋ฏ๋ก ๊ฐฑ์ ํ๋คโญ
... (์๋ต)4 -> 4
vs4 -> <1> -> 4
- k = 2 / ๊ฒฝ์ ์ง๊ฐ <2>์ธ ๊ฒฝ์ฐ
1 -> 1
vs1 -> <2> -> 1
1 -> 2
vs1 -> <2> -> 2
1 -> 3
vs1 -> <2> -> 3
... (์๋ต)4 -> 1
vs4 -> <2> -> 1
โญ๊ฒฝ์ ์ง๋ฅผ ์ง๋ ๋๊ฐ ๋ ์ต์๊ฐโญ4 -> 2
vs4 -> <2> -> 2
4 -> 3
vs4 -> <2> -> 3
โญ๊ฒฝ์ ์ง๋ฅผ ์ง๋ ๋๊ฐ ๋ ์ต์๊ฐโญ4 -> 4
vs4 -> <2> -> 4
- k = 3, k = 4์ ๋ํด์๋ ๋ฐ๋ณตํ๋ฉด ์ต์ข ์ ์ผ๋ก ์๋๊ณผ ๊ฐ์ ๊ฒฐ๊ณผ๊ฐ ๋์จ๋ค!
- ์ด๊ฒ์ด ๋ฐ๋ก ์ต์ข ์ ์ผ๋ก ๋ชจ๋ ์ ์ ์ฌ์ด์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ํ๋ ฌ๋ก ํํํ, ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ต์ข ๊ฒฐ๊ณผ์ด๋ค :D
def make_graph(n, arr):
# ์๊ธฐ์์ ์ผ๋ก ๊ฐ๋ ๊ฐ์ ์ 0์ผ๋ก, ๋๋จธ์ง๋ ๋ฌดํ๋๋ก ์ด๊ธฐํ
graph = [[0 if (i == j) else float("inf") for i in range(n)] for j in range(n)]
for u, v, w in arr:
graph[u - 1][v - 1] = w
return graph # ์ธ์ ํ๋ ฌ์ผ๋ก ๋ง๋ ํ ๋ฆฌํด
def floyd_warshall(n, arr):
# 1. ์ธ์ ํ๋ ฌ๋ก ๋ํ๋ด๊ธฐ
graph = make_graph(n, arr)
# 2. [๊ฒฝ์ ์ง(k)๋ฅผ ์ง๋๋ ์ต๋จ ๊ฑฐ๋ฆฌ] vs [๊ฒฝ์ ์ง(k)๋ฅผ ์ง๋์ง ์๋ ์ต๋จ ๊ฑฐ๋ฆฌ]
# ๋ ๊ผญ์ง์ ๊ฐ์ ์ถ์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ต์ ์ด ๋ ๋๊น์ง ์ ์ง์ ์ผ๋ก ๊ฐ์ ์์ผ์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ์ฐพ์.
for k in range(n):
for i in range(n):
for j in range(n):
if graph[i][k] + graph[k][j] < graph[i][j]:
graph[i][j] = graph[i][k] + graph[k][j]
return graph
โญ์ ๋ ฅโญ
# n์ ์ ์ ๊ฐ์ / arr์ [์์ ์ ์ , ๋์ฐฉ ์ ์ , ๊ฐ์ค์น(๊ฑฐ๋ฆฌ)]
n = 4
arr = [[1, 3, -2], [3, 4, 2], [4, 2, -1], [2, 1, 4], [2, 3, 3]]
answer = floyd_warshall(n, arr)
# ์ถ๋ ฅํด๋ณด๊ธฐ
for ans in answer:
print(ans)
โญ์ถ๋ ฅโญ