union-find
-
[Algorithm] Union - Find (์ ๋์จ ํ์ธ๋)๋?Algorithm 2020. 9. 6. 02:38
์ด ๊ธ์ (https://m.blog.naver.com/ndb796/221230967614) ๋ธ๋ก๊ทธ๋ฅผ ๋ณด๊ณ ์์ฑํ์์ต๋๋ค. Union Find ์ ๋์จ ํ์ธ๋๋ ๋ํ์ ์ธ ๊ทธ๋ํ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. ์ฌ๋ฌ ๊ฐ์ ๋ ธ๋๊ฐ ์์ ๋ ๋ ๊ฐ์ง์ ๋ ธ๋ ํ๋์ ๊ทธ๋ํ๋ก ์ฐ๊ฒฐ๋์ด ์๋์ง ํ๋ณํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. ๋จผ์ , ๋ฐฐ์ด์ ๋ง๋ค์ด์ ํด๋น ๋ ธ๋๋ฒํธ๋ก ๋ถ๋ชจ ๋ ธ๋๋ฒํธ๋ฅผ ๊ฐ๋ฆฌํค๊ฒ ํฉ๋๋ค. ์ฒ์์๋ ๋น์ฐํ ์ฐ๊ฒฐ๋ ๊ทธ๋ํ๊ฐ ์๊ธฐ ๋๋ฌธ์ ๊ฐ์ ์์ ์ ๋ ธ๋๋ฒํธ๋ฅผ ๊ฐ๋ฆฌํค๊ฒ ๋ฉ๋๋ค. 1๊ณผ 2๋ฅผ ์ฐ๊ฒฐํ๊ฒ ๋๋ฉด ํฉ์น๋ค๋ ๋ป์์ Union์ด๋ผ๊ณ ๋ถ๋ฅด๊ณ ๋ ธ๋๋ฒํธ ์ค ์์ ๋ ธ๋๋ฒํธ๊ฐ ๋ถ๋ชจ๋ ธ๋๊ฐ ๋ฉ๋๋ค. ์ด๋ ๊ฒ๋ง ๊ตฌํํ ๊ฒฝ์ฐ 2์ 3์ด ์ฐ๊ฒฐํ๊ฒ ๋๋ฉด ๋ถ๋ชจ๋ ธ๋๊ฐ 2๊ฐ ๋๋๋ฐ 1๊ณผ 3์ด ๊ฐ์ ๊ทธ๋ํ๋ก ์ฐ๊ฒฐ๋์ด ์๋์ง๋ ์ ์๊ฐ ์์ต๋๋ค. ๋ฐ๋ผ์ ์ฌ๊ทํจ์๋ฅผ..