Algorithm
2022. 1. 8.
[Swift] Union-Find ์๋ฃ๊ตฌ์กฐ ๊ตฌํํด๋ณด๊ธฐ
Union-Find ์๋ฃ๊ตฌ์กฐ ๊ฐ๋
Union-Find๋ ์๋ก์ ๋ถ๋ถ์งํฉ ๊ตฌ์กฐ๋ก ๋๋์ด์ง ๋ฐ์ดํฐ๋ค์ ๋ค๋ฃจ๋ ์๋ฃ๊ตฌ์กฐ์
๋๋ค. ์ฌ๊ธฐ์ ์๋ก์ ๋ถ๋ถ์งํฉ์ด๋?? ์ํ์ ์ผ๋ก ํํํ๋ฉด, {1,2}, {3,4}, {5,6} ๊ณผ ๊ฐ์ด ์๋ก ๋ค๋ฅธ ์์๋ค์ ๊ฐ์ง ์งํฉ๋ค ์ฌ์ด ๊ด๊ณ๋ฅผ ์๋ฏธํฉ๋๋ค. 3๊ฐ์ง ์งํฉ์์ ์๋ก ๊ณตํต๋ ์์๊ฐ ์์ผ๋ฉด ์๋ก์ ๋ถ๋ถ์งํฉ์ด๋ผ๊ณ ํฉ๋๋ค. ๊ทธ๋ผ ์ด๋ฅผ ์ด๋ป๊ฒ ๊ตฌํํ ๊น์? ๋๊ฐ์ง ํจ์์ ํ๊ฐ์ ๋ฐฐ์ด๋ก ๊ตฌํํด๋ณผ ์ ์์ต๋๋ค. Parent ๋ฐฐ์ด ๋จผ์ , ์๊ธฐ ์์ ์ ๊ฐ๋ฆฌํค๋ parent ๋ฐฐ์ด ํ๊ฐ๋ฅผ ๋ง๋ค์ด์ค๋๋ค. 0 1 2 3 4 5 0 1 2 3 4 5 ์ด parent ๋ฐฐ์ด์ ์์ ์ ๋ถ๋ชจ๋ฅผ ๊ฐ๋ฆฌํต๋๋ค. ์ฒ์ ์์์ ๋ชจ๋ ๊ฐ์ ์๊ธฐ์์ ์ ๋ถ๋ชจ๋ก ๊ฐ์ง๊ณ ์์ต๋๋ค. findParent(A) A์์์ ๋ถ๋ชจ๊ฐ ์ด..