ํธ๋ฆฌ ํ์ ์๊ณ ๋ฆฌ์ฆ - ์ ๋์จ ํ์ธ๋
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๋ก๋ ๊ตฌํ์ด ๊ฐ๋ฅํ์ง๋ง ์ ๋์จ ํ์ธ๋๋ฅผ ์ด์ฉํ์ฌ ์ฐ๊ฒฐ ๊ฐ์๋ฅผ ์ฒดํฌํ๋ ๋ฐฉ์์ผ๋ก ๊ตฌํ๋ ๊ฐ๋ฅํ๋ค.
์ค๋๋ ์ด์ฝ๐ฅ
'SW์ฌ๊ดํ๊ต ์ ๊ธ > ๊ฐ๋ฐ์ผ์ง - TIL' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Week04] ์๊ณ ๋ฆฌ์ฆ - ๋นํธ ๋ง์คํน (2) | 2022.04.26 |
---|---|
[Week03] ์๊ณ ๋ฆฌ์ฆ - DFS / BFS ๋ฐฑ์ค ๋ฌธ์ (5) | 2022.04.21 |
[Week02] ์๊ณ ๋ฆฌ์ฆ - ํ (feat. python) (2) | 2022.04.14 |
[Week02] ์๊ณ ๋ฆฌ์ฆ - ์ด๋ถํ์ (5) | 2022.04.09 |
[Week01] ์๊ณ ๋ฆฌ์ฆ - ์ ๋ ฌ01 (0) | 2022.04.09 |
๋๊ธ