์ ๋์จ ํ์ธ๋ ํ์ด์ฌ ๊ตฌํํ๊ธฐ / union - find by Phython
์ ๋์จ / ํ์ธ๋๋ ํ์ฌ ๋ ธ๋๋ค์ด ๊ฐ์ ๊ทธ๋ฃน์ ์ํด ์๋์ง ํ์ธํ๊ณ ๊ฐ์ ๊ทธ๋ฃน์ผ๋ก ๋ง๋๋ ๋ณํฉ์ด ํ์ํ ๋ ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค.
find ์๊ณ ๋ฆฌ์ฆ ๊ตฌํ
par = [ -1 for i in range(N + 1) ] # ๋ฃจํธ๋ฅผ ๋ด์ ๋ฐฐ์ด
def find(x): # ๋ฃจํธ๋ฅผ ์ฐพ์์ฃผ๋ ํจ์
if par[x] < 0: # ์์ง ๋ฃจํธ๊ฐ ์๋ค๋ฉด
return x # ์๊ธฐ ์์ ์ด ๋ฃจํธ => ์์ง ์ฐ๊ฒฐ๋ ์ ์ด ์์
par[x] = find(par[x]) # ์์ ์ ๋ถ๋ชจ๋ฅผ ๋ถ๋ชจ->๋ถ๋ชจ ๋ฅผ ์ฌ๊ท๋ก ๋ฃจํธ ๋ถ๋ชจ๋ฅผ ์ฐพ์
return par[x] # ๋ฃจํธ ๋ถ๋ชจ๋ฅผ ๋ฆฌํด
par ์ด๋ผ๋ ๋ฐฐ์ด์๋ ๊ฐ ๋ ธ๋์ ๋ถ๋ชจ๋ฅผ ๋ด์ ๋์ต๋๋ค.
par ๋ฐฐ์ด์ index๋ ๊ฐ ๋ ธ๋์ ๋ฒํธ์ด๊ณ ๊ทธ ๊ฐ์ ๋ถ๋ชจ ๋ ธ๋๋ฅผ ์๋ฏธํฉ๋๋ค.
์ฒ์ ๋ชจ๋ ๋ ธ๋์ ๊ฐ์ -1(์์ง ๋ถ๋ชจ๊ฐ ์ ํด์ง์ง ์์)์ผ๋ก ์ด๊ธฐํํฉ๋๋ค. -> ๋ชจ๋ ๋ ธ๋(index)๋ ์์ง ๋ถ๋ชจ ๋ ธ๋๊ฐ ์์(-1)
find ํจ์๋ ์ฌ๊ท์ ์ผ๋ก ์์ ์ ๋ถ๋ชจ์ ๋ถ๋ชจ๋ฅผ ํ์ํฉ๋๋ค. ์ต์ข ์ ์ผ๋ก ๋ถ๋ชจ๊ฐ ์๋ ๋ ธ๋(๊ฐ์ด -1์ธ ๋ ธ๋)๋ฅผ ๋ฐ๊ฒฌํ๋ค๋ฉด ์ต์์ ๋ ธ๋(root)๋ก ๋ณผ ์ ์์ต๋๋ค.
์ต์์ ๋ ธ๋๋ฅผ ์ฐพ์๋ค๋ฉด ํด๋น ๋ ธ๋์ ๊ฐ์ ๋ฆฌํดํ๊ณ ๊ทธ ์ด์ ์ ๋ ธ๋๋ค์ ์ต์์ ๋ ธ๋์ ๋ฒํธ๋ก ์์ ์ ๋ถ๋ชจ ๋ ธ๋๋ฅผ ๊ฐฑ์ ํ๊ฒ ๋ฉ๋๋ค.
union ์๊ณ ๋ฆฌ์ฆ ๊ตฌํ
def union(a, b): # union ๋ ์งํฉ์ ์ฐ๊ฒฐํด์ฃผ๋ ํจ์
a, b = find(a), find(b)
if a == b: # ๋ฃจํธ ๋ถ๋ชจ๊ฐ ๊ฐ๋ค๋ฉด ๊ฐ์ ์งํฉ => ์ด๋ฏธ ์ฐ๊ฒฐ ๊ด๊ณ
return False
par[b] = a # ๋ถ๋ชจ ๋
ธ๋๋ฅผ ํต์ผ์์ผ ํ๋์ ์งํฉ์ผ๋ก ๋ณํฉ
return True
union ํน์ merge ์๊ณ ๋ฆฌ์ฆ์ ๋ ๋ ธ๋๋ฅผ ์ธ์๋ก ๋ฐ์์ ํด๋น ๋ ธ๋๋ค์ด ๊ฐ์ ๊ทธ๋ฃน์ธ์ง ํ์ธํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค.
find ํจ์๋ฅผ ํตํด์ ํด๋น ๋ ธ๋์ ๋ถ๋ชจ ๋ ธ๋๋ฅผ ํ์ธํฉ๋๋ค.
์ ํจ์์์๋ ์ธ์๋ก ๋ฐ์ a, b๋ณ์์ ๋ถ๋ชจ์ ๋ ธ๋์ ๊ฐ์ ๋์ ํด ์ฃผ์์ต๋๋ค. (์ธ์๋ก ๋ฐ์ ๊ฐ์ ์ง์ญ๋ณ์ ์ด๋ฏ๋ก ์๋ณธ a, b ๊ฐ ๋ณํ์ง๋ ์์ต๋๋ค.)
๋ง์ฝ ๋ถ๋ชจ์ ๊ฐ์ด ๊ฐ๋ค๋ฉด ๊ฐ์ ์ด๋ฏธ ๊ฐ์ ๊ทธ๋ฃน์ด๊ธฐ์ 'False'๋ฅผ ๋ฆฌํดํ์ฌ ํจ์๋ฅผ ์ข ๋ฃํฉ๋๋ค.
๊ทธ๋ ์ง ์๋ค๋ฉด, ๋ค๋ฅธ ๋ ธ๋์ด๋ฏ๋ก ๋ณํฉ์ ์ํด์ ํ์ชฝ์ ๋ถ๋ชจ ๋ ธ๋๋ฅผ ๋ค๋ฅธ ๋ ธ๋์ ๋ถ๋ชจ ๋ ธ๋๋ก ๊ฐฑ์ ํฉ๋๋ค. (์ด๋ ๊ฒ์ด๋ ์๊ด์์ต๋๋ค.)
๊ฐฑ์ ํ ๊ฐ์ ๊ฐฑ์ ์ ํ์๋ค๋ ์๋ฏธ๋ก 'True'๋ฅผ ๋ฆฌํดํฉ๋๋ค.
union ํจ์์ ๋ชฉ์ ์ ๋ ๋ถ๋ชจ ๋ ธ๋๋ฅผ ๋์ผํ๊ฒ ๋ง๋ค์ด ํ๋์ ๊ทธ๋ฃน์์ ํ์ธํ ์ ์๋ ์ํ๋ก ๋ง๋๋ ๊ฒ์ ์์ต๋๋ค. ๋ฐ๋ผ์ return ๊ฐ์ ๊ฒฝ์ฐ ํ์์ ๋ฐ๋ผ์ ์์ ํ ์ ์์ต๋๋ค.