union-find

โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

6. Union Find(ํ•ฉ์ง‘ํ•ฉ ์ฐพ๊ธฐ) : MST - 1

Union Find (ํ•ฉ์ง‘ํ•ฉ ์ฐพ๊ธฐ) MST - 1 ์ •๋ง ์˜ค๋žœ๋งŒ์— ํฌ์ŠคํŒ…์ด๋‹ค. MST ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ํ’€๋˜ ๋„์ค‘ ์ƒ๊ฐ๋‚˜์„œ ํฌ์ŠคํŒ… ํ•˜๊ฒŒ ๋๋‹ค. ๋งค์ฃผ ์ฃผ๋ง๋งˆ๋‹ค ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋… ์ •๋ฆฌ๋ฅผ ํ•˜๋ ค๊ณ  ํ•˜๋Š”๋ฐ ๊ณ„์† ์‹คํŒจํ•˜๋Š” ๊ฒƒ ๊ฐ™๋‹ค... ใ…Žใ…Ž;; ์˜ค๋Š˜ ๋‹ค๋ค„๋ณผ ์ฃผ์ œ๋Š” MST, ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ๊ธฐ๋ณธ ๋ฒ ์ด์Šค์ธ Union Find์ด๋‹ค. ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•์—๋Š” ๋Œ€ํ‘œ์ ์œผ๋กœ ํฌ๋ฃจ์Šค์นผ(Kruskal)๊ณผ ํ”„๋ฆผ(Prim) ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์กด์žฌํ•œ๋‹ค. Union FInd๋Š” ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ•ต์‹ฌ์ด๋ผ๊ณ  ๋งํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋Ÿผ Union Find๊ฐ€ ๋ฌด์—‡์ธ์ง€ ์•Œ์•„๋ณด์ž. Union Find๋Š” ๋ง ๊ทธ๋Œ€๋กœ Union, ์ง‘ํ•ฉ์„ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๊ทธ๋ž˜ํ”„ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ ์ด๋“ค ๊ฐ„์˜ ๊ด€๊ณ„๋ฅผ ์•Œ์•„๋ณผ ์ˆ˜ ์žˆ๋‹ค. ๋ฐ”๋กœ ์˜ˆ์‹œ..

kodo_o
'union-find' ํƒœ๊ทธ์˜ ๊ธ€ ๋ชฉ๋ก