์ต์์ ์ฅํธ๋ฆฌ(2)
-
[ํ๋ก๊ทธ๋๋จธ์ค] ์ฌ ์ฐ๊ฒฐํ๊ธฐ
ํ๋ก๊ทธ๋๋จธ์ค์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.programmers.co.kr ๐ฌ ๋ฌธ์ ์ค๋ช ์ฐ๊ฒฐ๋์ด ์๋ ๋ ์ ์ ์ ๋ณด์ ๊ฐ์ค์น ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋ ์ต์ ๋น์ฉ(๊ฐ์ ์ ๊ฐ์ค์น์ ํฉ)์ผ๋ก ๋ชจ๋ ์ฌ์ ์ฐ๊ฒฐํ๊ณ ํด๋น ์ต์ ๋น์ฉ์ ๋ฐํํ๋ผ. ๐ ์ฃผ์ ์ฌํญ๋ชจ๋ ์ฌ ์ฐ๊ฒฐ + ์ต์ ๋น์ฉ → ์ต์ ์ ์ฅ ํธ๋ฆฌ(MST) ๊ตฌ์ฑ ๐ ๋ฌธ์ ํ์ด๋ชจ๋ ์ฌ์ ์ต์ ๋น์ฉ์ผ๋ก ์ฐ๊ฒฐํด์ผ ํ๋ฏ๋ก ์ต์ ์ ์ฅ ํธ๋ฆฌ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด์ผ ํ๋ค.๊ฐ์ ์ ๋ณด๋ฅผ ์๋ ค์ฃผ๊ณ ์์ผ๋ฏ๋ก ๊ฐ์ ๋ฐฐ์ด๋ก ๋ง๋ค์ด์ ์ฌ์ฉํ์.๊ฐ์ ๋ฐฐ์ด์ด๋ฏ๋ก ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด์ผ๊ฒ ๋ค!๊ฐ์ ๋ฐฐ์ด์ ๊ฐ์ค์น๋ก ์ค๋ฆ์ฐจ ์ ์ ๋ ฌ๋ชจ๋ ๊ฐ์ ์ด ์ฐ๊ฒฐ๋ ๋๊น์ง union-fin..
2024.09.05 -
[์๊ณ ๋ฆฌ์ฆ] ์ต์ ์ ์ฅ ํธ๋ฆฌ - ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ
์ ์ฅ ํธ๋ฆฌ(Spanning Tree) ์๋ ๊ทธ๋ํ์ ๋ชจ๋ ๋ ธ๋๊ฐ ์ฐ๊ฒฐ๋์ด ์์ผ๋ฉด์ ํธ๋ฆฌ์ ์์ฑ์ ๋ง์กฑํ๋ ๊ทธ๋ํ ์ ์ฅ ํธ๋ฆฌ์ ์กฐ๊ฑด ๋ณธ๋์ ๊ทธ๋ํ์ ๋ชจ๋ ๋ ธ๋๋ฅผ ํฌํจํด์ผ ํจ ๋ชจ๋ ๋ ธ๋๊ฐ ์๋ก ์ฐ๊ฒฐ ํธ๋ฆฌ์ ์์ฑ์ ๋ง์กฑ์ํด (์ฌ์ดํด์ด ์กด์ฌํ์ง ์์) ์ต์ ์ ์ฅ ํธ๋ฆฌ(Minimum Spanning Tree, MST) ๊ฐ๋ฅํ Spanning Tree ์ค์์, ๊ฐ์ ์ ๊ฐ์ค์น ํฉ์ด ์ต์์ธ Spanning Tree๋ฅผ ์ง์นญํจ ์ต์ ์ ์ฅ ํธ๋ฆฌ ์๊ณ ๋ฆฌ์ฆ ๊ทธ๋ํ์์ ์ต์ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ์ฐพ์ ์ ์๋ ์๊ณ ๋ฆฌ์ฆ์ด ์กด์ฌํจ ๋ํ์ ์ธ ์ต์ ์ ์ฅ ํธ๋ฆฌ ์๊ณ ๋ฆฌ์ฆ Kruskal’s algorithm(ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ), Prim's algorithm(ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ) ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ(Kruskal's algorithm) ๋ชจ๋ ์ ์ ์ ๋ ๋ฆฝ์ ์ธ..
2021.06.09