[BOJ][๐ก4][๋ฐฑ์ค#11404] ํ๋ก์ด๋
์์ฑ:    
์ ๋ฐ์ดํธ:
์นดํ ๊ณ ๋ฆฌ: BOJ Gold IV
๋ฌธ์ ์ถ์ฒ
๋ฌธ์
n(2ย โค n โค 100)๊ฐ์ ๋์๊ฐ ์๋ค. ๊ทธ๋ฆฌ๊ณ ํ ๋์์์ ์ถ๋ฐํ์ฌ ๋ค๋ฅธ ๋์์ ๋์ฐฉํ๋ m(1 โค m โค 100,000)๊ฐ์ ๋ฒ์ค๊ฐ ์๋ค. ๊ฐ ๋ฒ์ค๋ ํ ๋ฒ ์ฌ์ฉํ ๋ ํ์ํ ๋น์ฉ์ด ์๋ค. ๋ชจ๋ ๋์์ ์ (A, B)์ ๋ํด์ ๋์ A์์ B๋ก ๊ฐ๋๋ฐ ํ์ํ ๋น์ฉ์ ์ต์๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋์์ ๊ฐ์ n์ด ์ฃผ์ด์ง๊ณ ๋์งธ ์ค์๋ ๋ฒ์ค์ ๊ฐ์ m์ด ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ์ ์งธ ์ค๋ถํฐ m+2์ค๊น์ง ๋ค์๊ณผ ๊ฐ์ ๋ฒ์ค์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ๋จผ์ ์ฒ์์๋ ๊ทธ ๋ฒ์ค์ ์ถ๋ฐ ๋์์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ๋ฒ์ค์ ์ ๋ณด๋ ๋ฒ์ค์ ์์ ๋์ a, ๋์ฐฉ ๋์ b, ํ ๋ฒ ํ๋๋ฐ ํ์ํ ๋น์ฉ c๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ์์ ๋์์ ๋์ฐฉ ๋์๊ฐ ๊ฐ์ ๊ฒฝ์ฐ๋ ์๋ค. ๋น์ฉ์ 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ์์ ๋์์ ๋์ฐฉ ๋์๋ฅผ ์ฐ๊ฒฐํ๋ ๋ ธ์ ์ ํ๋๊ฐ ์๋ ์ ์๋ค.
์ถ๋ ฅ
n๊ฐ์ ์ค์ ์ถ๋ ฅํด์ผ ํ๋ค. i๋ฒ์งธ ์ค์ ์ถ๋ ฅํ๋ j๋ฒ์งธ ์ซ์๋ ๋์ i์์ j๋ก ๊ฐ๋๋ฐ ํ์ํ ์ต์ ๋น์ฉ์ด๋ค. ๋ง์ฝ, i์์ j๋ก ๊ฐ ์ ์๋ ๊ฒฝ์ฐ์๋ ๊ทธ ์๋ฆฌ์ 0์ ์ถ๋ ฅํ๋ค.
์์
์ ๋ ฅ
5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4
์ถ๋ ฅ
0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0
My Sol
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
mat = [[1e8]*(N+1) for _ in range(N+1)]
for _ in range(M):
a, b, c = map(int, input().split())
if mat[a][b] > c:
mat[a][b] = c
for k in range(1, N+1):
for i in range(1, N+1):
for j in range(1, N+1):
if i != j and mat[i][j] > mat[i][k] + mat[k][j]:
mat[i][j] = mat[i][k] + mat[k][j]
for i in range(1, N+1):
for j in range(1, N+1):
if mat[i][j] == 1e8:
mat[i][j] = 0
print(mat[i][j], end=' ')
print()
์๋ํ๋ ๋ค๋ฅธ ๋ฌธ์ ์์ ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ฒ์์ผ๋ก ์๊ฒ ๋์ด ์ด๋ฅผ ์ฐธ๊ณ ํด์ ํ์๋ค. ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ์ O(N3)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค. n๊ฐ์ ๋ ธ๋๊ฐ ์์ ๋ n๋ฒ๋์ i์์ j๋ฅผ ๋ฐ๋ก ๊ฐ ๊ฒ์ ๋ค๋ฅธ ๊ฒฝ๋ก๋ก ๊ฒฝ์ ์์ ๋ ๋น ๋ฅธ ๊ฒฝ๋ก๊ฐ ์์ ๊ฒ์ธ์ง๋ฅผ ํ๋จํ๋ ๊ฒ์ด๋ค. 3์ค for๋ฌธ์ ๋๋ฆฌ๋ฉฐ ๋์์ ๊ฐ ๊ฒฝ๋ก๊ฐ ์ง์ ๊ฒฝ๋ก๋ณด๋ค ๋น ๋ฅธ ๊ฒฝ์ฐ ์ด๋ฅผ ๊ฐฑ์ ํด์ฃผ๋ ๋ฐฉ์์ด๋ค.
๊ฒฐ๊ณผ
๋ง์์ต๋๋ค!!
3๋ฌ ์ ์ ์ด ๋ฌธ์ ๋ฅผ multi dijkstra ๋ฌธ์ ๋ผ๊ณ ์ ์ด๋๊ณ ๋์ด๊ฐ์๋๋ฐ, ํด๊ฒฐ์ฑ ์ ์ฐ์ฐํ ์๊ฒ๋๋ ๊ธฐ๋ถ์ด ์ข๋ค. ์ญ์ ์๊ณ ๋ฆฌ์ฆ์ ๋ต์ ๋ณด๋ฉฐ ์ฑ์ฅํ๋ ๊ฒ ๊ฐ๋ค.
๋๊ธ๋จ๊ธฐ๊ธฐ