๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
SW์‚ฌ๊ด€ํ•™๊ต ์ •๊ธ€/๊ฐœ๋ฐœ์ผ์ง€ - TIL

[Week03] ์•Œ๊ณ ๋ฆฌ์ฆ˜ - ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ

by young-ji 2022. 4. 20.

 

ํŠธ๋ฆฌ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ - ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ
Union Find

 

โœ… ๊ฐœ๋… / ์›๋ฆฌ

: ๋Œ€ํ‘œ์ ์ธ ํŠธ๋ฆฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ 

: ํ•ฉ์ง‘ํ•ฉ ์ฐพ๊ธฐ, ์„œ๋กœ์†Œ ์ง‘ํ•ฉ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ด๋ผ๊ณ ๋„ ๋ถ€๋ฅธ๋‹ค. 

 

์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ๋Š” ์ง‘ํ•ฉ(set)์„ ํ•ฉํ•˜๊ธฐ์œ„ํ•œ ์—ฐ์‚ฐ์ด๋‹ค. 

์–‘๋ฑกํ–ฅ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•ด ํ•ฉ์ง‘ํ•ฉ ์—ฐ์‚ฐ ๊ตฌํ˜„์ด ๊ฐ€๋Šฅํ•˜์ง€๋งŒ ์‹œ์ž‘ ๋ณต์žก๋„๊ฐ€ ์•ˆ์ข‹์•„ ํŠธ๋ฆฌ ํ˜•ํƒœ๋ฅผ ํ™œ์šฉํ•œ๋‹ค. 

๋ถ€๋ชจ๋ฅผ ๊ฐ€๋ฅดํ‚ค๋Š” ํŠธ๋ฆฌ์ฒ˜๋Ÿผ ๋งํฌ๋ฅผ ๋งŒ๋“ค์–ด ์ง‘ํ•ฉ์„ ํ‘œํ˜„ํ•œ๋‹ค. 

 

ํ•˜๋‚˜์˜ ํŠธ๋ฆฌ๊ฐ€ ํ•˜๋‚˜์˜ set์ด๋ฉฐ ํŠธ๋ฆฌ์˜ parents๋ฅผ ์ฐพ์•„ ์˜ฌ๋ผ๊ฐ€ ๋ฃจํŠธ๋ฅผ ๋งŒ๋‚˜๋ฉด ๋ฃจํŠธ๊ฐ’์ด ์ง‘ํ•ฉ์˜ ๋Œ€ํ‘œ๊ฐ’์ด๋‹ค.

๋‘๊ฐœ์˜ ์ง‘ํ•ฉ์— ๋ฃจํŠธ๊ฐ’์„ ์ฐพ์•„์„œ(find) ๋ฃจํŠธ๊ฐ’์ด ๋‹ค๋ฅด๋ฉด ํ•˜๋‚˜์˜ ํŠธ๋ฆฌ๋กœ ๋งŒ๋“ ๋‹ค.(union) 

> ํŠธ๋ฆฌ ๋†’์ด h๋งŒํผ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ–๋Š”๋‹ค. 

 

์ง‘ํ•ฉ์˜ ํ•ฉ์ง‘ํ•ฉ ์‹œํ‚จ๋‹ค๋Š” ๊ฐœ๋…์„ ์ƒ๊ฐํ•˜๋ฉด ๋ฌธ์ œ ํ’€๋•Œ ํ—ท๊ฐˆ๋ ค์„œ ์ฃผ์–ด์ง„ ๊ทธ๋ž˜ํ”„์˜ ๋ฃจํŠธ๋ฅผ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ •๋„๋กœ ์ดํ•ดํ•˜๊ณ  ๋„˜์–ด๊ฐ€๋ฉด ์–ด๋ ต์ง€์•Š๋‹ค. 

 

โœ… ๊ตฌํ˜„

find

#union find - ๋ถ€๋ชจ๋…ธ๋“œ๋ฅผ ์ฐพ๋Š” ํ•จ์ˆ˜
def getParent(x) :
    if parent[x] == x : return x
    parent[x] = getParent(parent[x])
    return parent[x]
    
#union find - ๊ฐ™์€ ๋ถ€๋ชจ๋ฅผ ๊ฐ€์ง€๋Š”์ง€ ํ™•์ธ
def findParent(a,b) :
    a = getParent(a)
    b = getParent(b)
    if a == b : return 0 #๊ฐ™์€ ๋ถ€๋ชจ๋ฅผ ๊ฐ€์ง€๊ณ ์žˆ๋‹ค. ์ฆ‰ ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ์ด๋‹ค. 
    return 1

union

#union find - ๋ถ€๋ชจ ๋…ธ๋“œ๋ฅผ ํ•ฉ์น˜๋Š” ํ•จ์ˆ˜
def unionParent(a,b) :
    a = getParent(a)
    b = getParent(b)
    if a < b : parent[b] = a
    else : parent[a] = b
    
#์—ฐ๊ฒฐ ๋…ธ๋“œ์— ๋ถ€๋ชจ๊ฐ€ ๋‹ค๋ฅด๋ฉด ๋ถ€๋ชจ ๋…ธ๋“œ๋ฅผ ํ•ฉ์ณ์ค€๋‹ค    
for i in p : # p๋Š” ๋…ธ๋“œ ๋ฆฌ์ŠคํŠธ 
    if findParent(i[0],i[1]) != 0:
        unionParent(i[0],i[1])

 

โ—๏ธparent ๋ฆฌ์ŠคํŠธ์— ์ €์žฅ๋œ ๊ฐ ๋ฃจํŠธ ๋…ธ๋“œ์— ๋‹ค์‹œ ํ•œ๋ฒˆ ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ๊ตฌํ•ด์ค€๋‹ค.

result = [] # ๊ฐ ๋…ธ๋“œ์— ๋ฃจํŠธ๋…ธ๋“œ๋ฅผ ์ €์žฅํ•œ๋‹ค. 
for a in parent :
    result.append(getParent(a))

 ์ด๋ฏธ ๋ฃจํŠธ ๋…ธ๋“œ๋กœ ์ง€์ •๋œ ์ง€์ •๋œ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ๋ณ€ํ•  ๊ฒฝ์šฐ ์ด๋ฏธ ๋ฆฌ์ŠคํŠธ์— ๋‹ด๊ธด ๋…ธ๋“œ๋Š” ๋ณ€๊ฒฝ๋˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ๊ตฌํ•ด์•ผํ•œ๋‹ค๋ฉด ์ด๋ถ€๋ถ„์„ ๊ผญ ์ถ”๊ฐ€ํ•ด์ฃผ์–ด์•ผํ•œ๋‹ค. 

์˜ˆ๋ฅผ ๋“ค๋ฉด 6์˜ ๋ฃจํŠธ๋…ธ๋“œ๊ฐ€ 3์œผ๋กœ ๋ณ€๊ฒฝ๋˜์—ˆ๋Š”๋ฐ ํ›„์— 3์˜ ๋ฃจํŠธ ๋…ธ๋“œ๊ฐ€ 1๋กœ ๋ฐ”๋€๋‹ค๋ฉด 6์˜ ๋ฃจํŠธ ๋…ธ๋“œ๋Š” 3์œผ๋กœ ๋‚จ์•„์žˆ๊ฒŒ๋œ๋‹ค. 

์ด๋•Œ๋ฌธ์— ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•ด์•ผํ•œ๋‹ค๋Š” ๊ธ€๋„ ๋ดค์ง€๋งŒ ์ดํŽธ์ด ๊ฐ„๋‹จํ•ด์„œ ์œ„์ฒ˜๋Ÿผ ๊ตฌํ˜„ํ•ด๋ดค๋‹ค.

( ์ž‘์€ ๋…ธ๋“œ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ๋ณ€๊ฒฝ๋˜๊ธฐ๋•Œ๋ฌธ์— ๋ฌธ์ œ ์—†์–ด๋ณด์ด์ง€๋งŒ ๋ฐ˜๋ก€๊ฐ€ ์žˆ์„์ง€๋„ ๋ชจ๋ฅด๊ฒ ๋‹ค. ๋ฐฑ์ค€์—์„œ๋Š” ๋ฌธ์ œ์—†์—ˆ๋‹ค. )

 

 

โœ… ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ ์—ฐ์Šต๋ฌธ์ œ

ํ•ฉ์ง‘ํ•ฉ์„ ์‹œํ‚จ๋‹ค๋Š” ๊ฐœ๋…์ด ์™€๋‹ฟ์ง€์•Š๋Š”๋‹ค๋ฉด ๊ฐ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ๋…ธ๋“œ๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ดํ•ดํ•˜๋ฉด๋œ๋‹ค.

 

https://www.acmicpc.net/problem/1197

 

1197๋ฒˆ: ์ตœ์†Œ ์ŠคํŒจ๋‹ ํŠธ๋ฆฌ

์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ V(1 ≤ V ≤ 10,000)์™€ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ E(1 ≤ E ≤ 100,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ E๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์„ธ ์ •์ˆ˜ A, B, C๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด๋Š” A๋ฒˆ ์ •์ ๊ณผ B๋ฒˆ ์ •์ ์ด

www.acmicpc.net

1. ์ตœ์†Œ ์ŠคํŒจ๋‹ ํŠธ๋ฆฌ 

์ŠคํŒจ๋‹ ํŠธ๋ฆฌ๋Š” ๋ชจ๋“  ์ •์ ์ด ์—ฐ๊ฒฐ๋˜์–ด์žˆ์œผ๋ฉด์„œ ์‚ฌ์ดํด ์—†๋Š” ํŠธ๋ฆฌ๋ฅผ ๋งํ•œ๋‹ค. ๋•Œ๋ฌธ์— n๊ฐœ์˜ ์ •์ ์— n+1๊ฐœ์˜ ๊ฐ„์„ ์„ ๊ฐ€์ง„๋‹ค. 

์ตœ์†Œ ์ŠคํŒจ๋‹ ํŠธ๋ฆฌ๋Š” kruskal์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ prim ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ํ•ด๊ฒฐ ๊ฐ€๋Šฅํ•˜๋‹ค.

> kruskal์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๊ฐ€์ค‘์น˜๊ฐ€ ์ž‘์€ ๊ฐ„์„ ๋ถ€ํ„ฐ ํ•˜๋‚˜์”ฉ ์ด์–ด๋‚˜๊ฐ€๋ฉฐ ๋ชจ๋“  ์ •์ ์„ ๋ฐฉ๋ฌธํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ฉฐ ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ๋ฅผ ์ด์šฉํ•˜์—ฌ ์‚ฌ์ดํด์˜ ์œ ๋ฌด๋ฅผ ์ฒดํฌํ•œ๋‹ค. 

 

 

https://www.acmicpc.net/problem/11724

 

11724๋ฒˆ: ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜

์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N๊ณผ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ M๊ฐœ์˜ ์ค„์— ๊ฐ„์„ ์˜ ์–‘ ๋์  u์™€ v๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ u, v ≤ N, u ≠ v) ๊ฐ™์€ ๊ฐ„์„ ์€ ํ•œ ๋ฒˆ๋งŒ ์ฃผ

www.acmicpc.net

2. ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜

๊ทธ๋ž˜ํ”„์˜ ์ •์ ๊ณผ ๊ฐ„์„ ์ด ์ฃผ์–ด์กŒ์„๋•Œ ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. 

DFS/BFS๋กœ๋„ ๊ตฌํ˜„์ด ๊ฐ€๋Šฅํ•˜์ง€๋งŒ ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ๋ฅผ ์ด์šฉํ•˜์—ฌ ์—ฐ๊ฒฐ ๊ฐœ์ˆ˜๋ฅผ ์ฒดํฌํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„๋„ ๊ฐ€๋Šฅํ•˜๋‹ค. 

 

์˜ค๋Š˜๋„ ์—ด์ฝ”๐Ÿ”ฅ

๋Œ“๊ธ€