ํ๋ก๊ทธ๋๋จธ์ค Level 3 - ์ฌ ์ฐ๊ฒฐํ๊ธฐ
๋ฌธ์ ํ๋ก๊ทธ๋๋จธ์ค - ์ฌ ์ฐ๊ฒฐํ๊ธฐ ํ์ด ๊ณผ์ ๋ชจ๋ ์ ์ ์ ์ฐ๊ฒฐํ๋ ์ต์ ์ ์ฅ ํธ๋ฆฌ(MST)๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค. ํ๋ฆผ๊ณผ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ํ์ฉํ ์ ์๋๋ฐ ์ด๋ฒ์๋ ํฌ๋ฃจ์ค์นผ์ ์ฌ์ฉํ๋ค. ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ์ ์ ๋ณด๋ค์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํด์ค ๋ค์, ์ฌ์ดํด์ ํ์ฑํ์ง ์๋ ๊ฐ์ ๋ค์ ํ์์ ์ผ๋ก ์ ํํด์ค๋ค. ์ด๋ฅผ ์ํ union-find ์๋ฃ๊ตฌ์กฐ๋ง ์ ๊ฒฝ์จ์ ๊ตฌํํ๋ฉด ๋ฌด๋ํ ํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ์ฝ๋ def union(p, u, v): u, v = find(p, u), find(p, v) if u == v: return p[u] = v def find(p, u): if p[u] == u: return u p[u] = find(p, p[u]) return p[u] def kruskal(v, edges): ans..
2021. 3. 1.