-
[Algorithm] ๋ค์ต์คํธ๋ผ(Dijkstra) ์๊ณ ๋ฆฌ์ฆAlgorithm 2020. 9. 8. 17:20๋ฐ์ํ
- ์ด ๊ธ์ (https://m.blog.naver.com/ndb796/221234424646) ๋ธ๋ก๊ทธ ๊ธ์ ์ฐธ๊ณ ํ์ฌ ์์ฑํ์์ต๋๋ค.
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ
๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ(DP)์ ํ์ฉํ ๋ํ์ ์ธ ์ต๋จ ๊ฒฝ๋ก ํ์ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. ๊ธฐ๋ณธ์ ์ผ๋ก ๋ค์ต์คํธ๋ผ๋ ํ๋์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ ๋ ์ด์ ์ ๊ตฌํ๋ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ฌ์ฉํ๋ค๋ ํน์ง๋๋ฌธ์ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋จ์ ํ์ฉํ๋ค๊ณ ๋ณผ ์ ์์ต๋๋ค.
- ์ถ๋ฐ ๋ ธ๋๋ฅผ ์ค์ ํฉ๋๋ค.
- ์ถ๋ฐ ๋ ธ๋์์ ๊ฐ ๋ ธ๋๊น์ง ๊ฐ๋ ์ต์ ๋น์ฉ์ ๋ฐฐ์ด์ ๋ง๋ค์ด ์ ์ฅํฉ๋๋ค.
- ๋ฐฉ๋ฌธํ์ง ์๋ ๋ ธ๋ ์ค์์ ๊ฐ์ฅ ๋น์ฉ์ด ์ ์ ๋ ธ๋๋ฅผ ์ ํํฉ๋๋ค.
- ํด๋น ๋ ธ๋๋ฅผ ๊ฑฐ์ณ์ ๊ฐ ๋ ธ๋๋ก ๊ฐ๋ ๊ฒฝ์ฐ๊น์ง ๋น๊ตํ์ฌ ์ต์ ๋น์ฉ์ ๊ฐฑ์ ํฉ๋๋ค.
- ์ ๊ณผ์ ์์ 3~4๋ฒ ๋ฐ๋ณตํฉ๋๋ค.
์ฌ๊ธฐ์ 3๋ฒ ๊ณผ์ ์์ ์ฝ๋ฉ ๊ตฌํ ์ ๋ฐฐ์ด์ ์์ ํ์ํด์ ์ต์ ๋น์ฉ ๋ ธ๋๋ฅผ ์ ํํ๋ ๋ฐฉ๋ฒ์ด ์๊ณ , ์ฐ์ ์์ ํ๋ฅผ ํ์ฉํ์ฌ ์ต์ ๋น์ฉ ๋ ธ๋๋ฅผ ์ ํํ๋ ๋ฐฉ๋ฒ์ด ์์ต๋๋ค. ์ ๋ ์ฐ์ ์์ ํ๋ฅผ ํ์ฉํ ๋ฐฉ๋ฒ์ ๋ํด ์๊ฐํด๋๋ฆฌ๊ฒ ์ต๋๋ค.
์์ ๊ฐ์ ๊ทธ๋ํ๋ ์ค์ ๋ก ์ปดํจํฐ์์ ํํํ ๋๋ ์ด์ฐจ์ ๋ฐฐ์ด๋ก ํํํด์ผ ํฉ๋๋ค.
1๋ฒ ๋ ธ๋๋ฅผ ์ถ๋ฐ ๋ ธ๋๋ฅผ ์ค์ ์ ํ๊ฒ ๋๋ฉด ํด๋น ๋ ธ๋๋ถํฐ ๊ฐ ๋ ธ๋๊น์ง ๊ฑฐ๋ฆฌ๋ฅผ ๋ค์๊ณผ ๊ฐ์ด 1์ฐจ์ ๋ฐฐ์ด๋ก ํํํฉ๋๋ค.
1๋ฒ ๋ ธ๋๋ฅผ ์ ์ธํ ๋ ธ๋ ์ค ๋ฐฉ๋ฌธํ์ง ์๋ ๋ ธ๋ ์ค ๊ฐ์ฅ ๋น์ฉ์ด ์ ์ ๋ ธ๋๋ฅผ ์ ํํด์ผ ํฉ๋๋ค. ๊ฐ์ฅ ์ต์ ๋น์ฉ์ ๊ณ์ ๊ณ์ฐํ๋ ๊ฒ๋ณด๋ค๋ ์ฐ์ ์์ ํ๋ฅผ ๋์ด ๋น์ฉ์ด ์ต์๊ฐ ๋๋ ๋ ธ๋๋ฅผ ์๋์ผ๋ก ์ ํํ ์ ์๊ฒ ๊ตฌํ์ ํ๋ฉด ์ข ๋ ์ฝ๊ฒ ๊ตฌํํ ์ ์์ต๋๋ค.
๋จ์ ๋ ธ๋๋ค ์ค์์ ๊ฐ์ฅ ์ต์ ๋น์ฉ ๋ ธ๋๋ฅผ ์ ํํฉ๋๋ค. ๋ฐ๋ผ์ ์ฐ์ ์์ ํ๋ฅผ ๊ณ ๋ คํ์ฌ 3๋ฒ ๋ ธ๋๊ฐ ์ ํ๋์์ต๋๋ค. 4๋ฒ ๋ ธ๋๋ฅผ ๊ฑฐ์ณ์ ๊ฐ๋ ๊ฒฝ์ฐ๋ฅผ ๋ชจ๋ ๊ณ ๋ คํ์ฌ ์ต์ ๋น์ฉ ๋ฐฐ์ด์ ๊ฐฑ์ ํ๋ฉด ๋ฉ๋๋ค.
์๋ ๋ ธ๋1์์ ๋ ธ๋5๊น์ง ๊ฐ๋ ๋น์ฉ์ INF ์์ต๋๋ค. ํ์ง๋ง ๋ ธ๋ 3์ ๊ฑฐ์ณ์ ๊ฐ๋ ๋น์ฉ์ 3์ด๋ฏ๋ก 3์ผ๋ก ๊ฐฑ์ ํฉ๋๋ค. ๊ฒฐ๊ณผ์ ์ผ๋ก ์ต์ ๋น์ฉ ๋ฐฐ์ด์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์ฐ์ ์์ ํ๋ ๋ค์๊ณผ ๊ฐ์ด ๊ฐฑ์ ์ด ๋๊ณ ์ด์ ๋ค์ ์ต์ ๋ ธ๋์ธ 2๋ฅผ ๊ฑฐ์ณ์ ๊ฐ๋ ๋น์ฉ์ ๋ชจ๋ ๊ฐฑ์ ํ๋ ๋ฐฉ์์ผ๋ก ๋ฐ๋ณตํ๋ฉด ๋ฉ๋๋ค.
์๋ ๋ ธ๋1์์ ๋ ธ๋4๊น์ง ๊ฐ๋ ๋น์ฉ์ 4 ์์ต๋๋ค. ํ์ง๋ง ๋ ธ๋ 2๋ฅผ ๊ฑฐ์ณ์ ๊ฐ๋ ๋น์ฉ์ 3์ด๋ฏ๋ก 3์ผ๋ก ๊ฐฑ์ ํฉ๋๋ค. ๊ฒฐ๊ณผ์ ์ผ๋ก ์ต์ ๋น์ฉ ๋ฐฐ์ด์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์ด์ ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก ๋ฐ๋ณตํ๋ค ๋ณด๋ฉด ์ต์ ๋น์ฉ ๋ฐฐ์ด์ ์์ฑ์ํฌ ์ ์์ต๋๋ค.
์ฝ๋
- ์ถ๊ฐ๋ก ๊ถ๊ธํ ์ ์ด๋ ์์ ํ ๋ถ๋ถ ์์ผ๋ฉด ๋๊ธ๋ก ๋จ๊ฒจ์ฃผ์ธ์.
๋ฐ์ํ'Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Algorithm] Kruskal Algorithm(ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ) (0) 2020.09.06 [Algorithm] Union - Find (์ ๋์จ ํ์ธ๋)๋? (0) 2020.09.06