์ฝ๋ฉํ
์คํธ/๊ธฐ๋ณธ ์๊ณ ๋ฆฌ์ฆ
2022. 2. 23.
์ต๋จ๊ฑฐ๋ฆฌ (Floyd_Warshall)
Floyd_Warshall 1.Floyd_Warshall ์ด๋ ํ๋ก์ด๋ ์์
์๊ณ ๋ฆฌ์ฆ์ '๋ชจ๋ ์ง์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ง์ ๊น์ง์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๋ชจ๋ ๊ตฌํด์ผํ ๊ฒฝ์ฐ' ์ฌ์ฉํ๋ค. ์ด์๊ฐ๋ณต์ก๋๋ O(n^3)์ผ๋ก ๋ง์ ๋
ธ๋๊ฐ ์ฃผ์ด์ง ๊ฒฝ์ฐ ์ฌ์ฉํ๊ธฐ ์ด๋ ต๋ค. ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ฅํ๊ธฐ ์ํด 1์ฐจ์ ๋ฆฌ์คํธ๋ฅผ ์ด์ฉํ ๋ค์ต์คํธ๋ผ์ ๋ค๋ฅด๊ฒ ๋ชจ๋ ๋
ธ๋์์ ๋ค๋ฅธ ๋ชจ๋ ๋
ธ๋๋ก ๊ฐ๋ ์ต๋จ๊ฑฐ๋ฆฌ ์ ๋ณด๋ฅผ ๋ด๊ธฐ์ํด 2์ฐจ์ ๋ฆฌ์คํธ๋ฅผ ์ฒ๋ฆฌํด์ผํ๋ค. ์ ํ์์ D(a,b) = min(D(a,b), D(a,k) + D(k,b) ์ด๋ค. (A์์ B๋ก๊ฐ๋ ์ต์๋น์ฉ๊ณผ A์์ K๋ฅผ ๊ฑฐ์ณ B๋ก ๊ฐ๋ ๋น์ฉ)์ ๋น๊ตํ์ฌ ๋ ์์๊ฐ์ผ๋ก ๊ฐฑ์ ํ๋ค. (์งํญ๊ณผ ๊ฒฝ์ ์ ๋น๊ต) 2.์์ ์ฝ๋ INF = int(1e9) n = int(input()) m = int(in..