๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Programming/Algorithm

[Algorithm] Union - Find (Python ๊ตฌํ˜„)

728x90
๋ฐ˜์‘ํ˜•

์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ ํŒŒ์ด์ฌ ๊ตฌํ˜„ํ•˜๊ธฐ / 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 ๊ฐ’์˜ ๊ฒฝ์šฐ ํ•„์š”์— ๋”ฐ๋ผ์„œ ์ˆ˜์ •ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

728x90
๋ฐ˜์‘ํ˜•