6. Union Find(ํฉ์งํฉ ์ฐพ๊ธฐ) : MST - 1
Union Find (ํฉ์งํฉ ์ฐพ๊ธฐ) MST - 1 ์ ๋ง ์ค๋๋ง์ ํฌ์คํ ์ด๋ค. MST ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ํ๋ ๋์ค ์๊ฐ๋์ ํฌ์คํ ํ๊ฒ ๋๋ค. ๋งค์ฃผ ์ฃผ๋ง๋ง๋ค ์๊ณ ๋ฆฌ์ฆ ๊ฐ๋ ์ ๋ฆฌ๋ฅผ ํ๋ ค๊ณ ํ๋๋ฐ ๊ณ์ ์คํจํ๋ ๊ฒ ๊ฐ๋ค... ใ ใ ;; ์ค๋ ๋ค๋ค๋ณผ ์ฃผ์ ๋ MST, ์ต์ ์ ์ฅ ํธ๋ฆฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ๊ธฐ๋ณธ ๋ฒ ์ด์ค์ธ Union Find์ด๋ค. ์ต์ ์ ์ฅ ํธ๋ฆฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ๋ฐฉ๋ฒ์๋ ๋ํ์ ์ผ๋ก ํฌ๋ฃจ์ค์นผ(Kruskal)๊ณผ ํ๋ฆผ(Prim) ์๊ณ ๋ฆฌ์ฆ์ด ์กด์ฌํ๋ค. Union FInd๋ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ํต์ฌ์ด๋ผ๊ณ ๋งํ ์ ์๋ค. ๊ทธ๋ผ Union Find๊ฐ ๋ฌด์์ธ์ง ์์๋ณด์. Union Find๋ ๋ง ๊ทธ๋๋ก Union, ์งํฉ์ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๊ทธ๋ํ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋ ์ด๋ค ๊ฐ์ ๊ด๊ณ๋ฅผ ์์๋ณผ ์ ์๋ค. ๋ฐ๋ก ์์..