μ μ
Union Findλ ν¬κ² λ κ°μ§ λͺ λ ΉμΌλ‘ μ΄λ£¨μ΄μ§λλ€.
Union(a, b)
- λ Έλ aμ bλ₯Ό κ°μ μΌλ‘ μ°κ²°ν©λλ€.
Connected(a, b)
- λ Έλ aμ bλ₯Ό μ°κ²°νλ κ²½λ‘κ° μ‘΄μ¬νλμ§ νμΈν©λλ€.
νμ©λλ μν©
- λ μ κ° μ°κ²°λμλμ§ νμΈνλ©΄μ κ°μ μ κ³μ μΆκ°ν΄λ³΄λ λμ μΈ μ
βΌοΈ κ·Έλν μ μ²΄κ° λ―Έλ¦¬ μ£Όμ΄μ§κ³ ννκ° λ³νμ§ μλ κ³ μ λ μ μ μΈ μν©μμλ μ μ νμ§ μμ΅λλ€.
βΌοΈ λ μ μ°κ²°νλ μ΅λ¨ κ²½λ‘ μ°Ύλ κ²κ³Όλ λ€λ₯Έ λ¬Έμ μ λλ€.
- μ°κ²° μνλ₯Ό μ‘°κΈμ© λ°μμ€λ λμμ μ°κ²° μνλ₯Ό νμΈνλ μν©
ex) μ»΄ν¨ν°λ§μμ λ μ₯λΉκ° μ°κ²°λμλμ§?
λΉνκΈ° λ Έμ λμμ μμμ λ μ§μμ΄ μ°κ²°λμλμ§?
ꡬν 첫λ²μ§Έ λ°©λ²
Union
κ³Ό Connected
λͺ
λ Ήμ μννκΈ° μν΄μλ κ·Έλνμ μ°κ²° μνμ μ μ₯μ΄ νμν©λλ€.
λ§μ½ μ΄λ₯Ό Adjacency list (μ°κ²° 리μ€νΈ) λ°©μμΌλ‘ μ μ₯νλ€λ©΄,
μλμ κ°μ μν©μμ Union
μ κ²½μ°μλ μμ μκ° μμ μνμ΄ κ°λ₯νμ§λ§,
Connected
λ μ΅μ
μ κ²½μ° λͺ¨λ κ°μ μ νμν΄μΌ ν©λλ€.
κ·Έλμ μ΄λ₯Ό κ°μ νκΈ° μν΄ λ Έλλ§λ€ μΈμ λ Έλλ₯Ό μ°κ²° 리μ€νΈλ‘ μ μ₯νμ§ μκ³
μλμ κ°μ΄ κ° λ Έλκ° Connected Componentμ μνλμ§λ₯Ό μ μ₯ν©λλ€.
Connected Component - μλ‘ μ°κ²°λ λ Έλλ€μ maximalν μ§ν©
Componentμ Idλ νΈμμ Componentμ μν λ
Έλ μ€ κ°μ₯ μμ λ²νΈλ₯Ό μ€μ νκ³ com[]
λ°°μ΄μ μ΄μ©ν΄ κ° λ
Έλκ° μ΄λ Componentμ μνλμ§ μ μ₯ν©λλ€.
μ΄ κ²½μ°μ Connect
λͺ
λ Ήμ μκ°ν΄λ³΄λ©΄ com[]
λ°°μ΄μ κ°μ΄ κ°μμ§λ§ νμΈνλ©΄ λμ΄ λΉ λ₯΄κ² λ΅μ μ»μ μ μμ΅λλ€. κ·Έλμ μ΄λ° λ°©μμ Quick-FindλΌκ³ ν©λλ€. νμ§λ§ Union
λͺ
λ Ή μμ ν Componentμ μνλ λ
Έλλ€μ com[]
κ°μ λͺ¨λ λ³κ²½ν΄μ£Όμ΄μΌ νλ€λ λ¨μ μ΄ μ‘΄μ¬ν©λλ€.
λ Έλκ° 6κ°μΈ μνμ Quick-Find ꡬν μ½λ
N = 6
# com λ°°μ΄ μ΄κΈ°ν
com = []
for idx in range(N):
com.append(idx)
def connected(p, q):
return com[p] == com[q]
# a, b μ€ (λ μμ κ°, λ ν° κ°) λ°ν
def minMax(a, b):
if a < b: return a, b
else: return b, a
def union(p, q):
id1, id2 = minMax(ids[p], ids[q])
for idx, _ in enumerate(com):
if com[idx] == id2: com[idx] = id1
Quick-Findμ Cost Model
λ°©μ | com[] μ΄κΈ°ν | union | connected (find) |
---|---|---|---|
Quick-Find | ~N | ~N | ~1 (μμ μκ°) |
Nκ°μ λ°°μ΄μ λͺ¨λ μ΄κΈ°νν΄μΌνκ³ , union
μμ Nκ°λ₯Ό λͺ¨λ νμΈν΄μΌνκΈ° λλ¬Έμ
λλ€.
Quick-Findμ ꡬ쑰μ ν΄μμ ν΅ν λλ²μ§Έ λ°©λ²
Quick-Findμμ Connected Componentλ₯Ό μ°κ²°λ λ©μ΄λ¦¬λ‘ μκ°νλ κ²μ μλμ κ°μ΄ Treeλ‘ λ°κΎΈμ΄ μκ°ν λ°©λ²μ λλ€.
μ΄λ κ² λλ©΄ union
μμ Componentμ μνλ λͺ¨λ λ
Έλμ com[]
κ°μ λ³κ²½νμ§ μκ³ μλμ κ°μ΄ rootλ§ μ―겨 λΆμ΄λ©΄ λκΈ° λλ¬Έμ union
μ μλκ° ν₯μλ©λλ€. (μμλ‘ μΌμͺ½μ νΈλ¦¬λ₯Ό μ€λ₯Έμͺ½ νΈλ¦¬λ‘ λΆμ΄λ λ°©μ)
union(1, 0)
connected
μ κ²½μ°μλ com[idx] == idx
μΈ rootλ₯Ό μ°Ύμκ° rootλΌλ¦¬ λΉκ΅νλ©΄ μ μμ μΌλ‘ μλν©λλ€.
μ΄ λ°©μμ union
μ΄ λΉ λ₯΄κ² μνλκΈ° λλ¬Έμ Quick-Unionμ΄λΌκ³ ν©λλ€.
λ Έλκ° 6κ°μΈ μνμ Quick-Union ꡬν μ½λ
N = 6
com = []
for idx in range(N):
com.append(idx)
def root(i):
while i != com[i]: i = com[i]
return i
def connected(p, q):
return root(p) == root(q)
def union(p, q):
id1, id2 = root(p), root(q)
com[id1] = id2
Quick-Unionμ Cost Model
λ°©μ | com[] μ΄κΈ°ν | union | connected (find) |
---|---|---|---|
Quick-Union | ~N | ~N | ~N |
μμμ Quick-Unionμ΄ union
μ μν μλκ° λΉ¨λΌμ‘λ€κ³ νλλ° Costκ° ~NμΈ κ²μ νμΈν μ μμ΅λλ€.
μ΄λ Treeκ° νμͺ½μΌλ‘ μΉμ°μ³μ depthκ° κΉμ΄μ§λ©΄ rootλ₯Ό μ°Ύλλ° μκ°μ΄ 걸리기 λλ¬Έμ connected
μ union
μ΄ μ€λ κ±Έλ¦¬κ² λ©λλ€.
Quick-Unionμ Tree depth λ¬Έμ ν΄κ²°ν μΈλ²μ§Έ λ°©λ²
Weighted Quick-Unionμ΄λΌκ³ λΆλ¦¬λ μ΄ λ°©λ²μ union
μμ μμ Treeμ rootλ₯Ό ν° Treeμ root μλμ λΆμμΌλ‘μ¨ Quick-Unionμμ Treeκ° νμͺ½μΌλ‘ μΉμ°μ³ depthκ° κΉμ΄μ§λ λ¬Έμ λ₯Ό ν΄κ²°ν λ°©λ²μ
λλ€.
ν° Treeμ root μλμ μμ Treeλ₯Ό λΆμμΌλ‘μ¨ λ§μ½ λ νΈλ¦¬μ ν¬κΈ°κ° κ°μ κ²½μ°μλ§ κΉμ΄κ° +1 λμ΄λκ³ , κ·Έλ μ§ μλ€λ©΄ μ΅λ κΉμ΄λ λμ΄λμ§ μκ² λ©λλ€. μ΄λ‘ μΈν΄ λͺ¨λ λ Έλκ° μ΄μ λ³΄λ€ rootμ λ κ°κΉμμ§κ² λ©λλ€.
λμ μ΄λ₯Ό ꡬννκΈ° μν΄μ Treeμ sizeλ₯Ό κΈ°λ‘ν΄μ€λλ€.
λ Έλκ° 6κ°μΈ μνμ Weighted Quick-Union ꡬν μ½λ
N = 6
com = []
size = []
for idx in range(N):
com.append(idx)
size.append(1)
def root(i):
while i != com[i]: i = com[i]
return i
def connected(p, q):
return root(p) == root(q)
def union(p, q):
id1, id2 = root(p), root(q)
if id1 == id2: return
if size[id1] <= size[id2]:
com[id1] = id2
size[id2] += size[id1]
else:
com[id2] = id1
size[id1] += size[id2]
Weighted Quick-Unionμ κΉμ΄ μ ν
Nκ°μ λ Έλ μ€ μμμ λ Έλλ₯Ό xλΌκ³ ν΄λ΄ μλ€.
xμ κΉμ΄κ° +1 λ λλ xκ° μν νΈλ¦¬κ° μμμ λ ν° νΈλ¦¬μ μ°κ²°λ λμ λλ€.
κ·Έλ κ² λλ©΄ xκ° μν νΈλ¦¬μ ν¬κΈ°λ μ΅μ 2λ°°κ° λ©λλ€. (κ°μ ν¬κΈ°μ νΈλ¦¬μ ν©μ³μ‘μ λ 2λ°°)
λ§μ½ xμ κΉμ΄κ° kλ² +1 κΉμ΄μ§λ€κ³ νμ λ,
xκ° μν νΈλ¦¬μ ν¬κΈ°λ μ΅μ ο»Ώ μ λλ€.
κ·Έλ°λ° μ 체 κ·Έλνμ Nκ°μ λ Έλλ§ μκΈ° λλ¬Έμ ο»Ώ β€ N μ λλ€.
κ·Έλ¬λ―λ‘ ο»Ώ , λ°λΌμ κΉμ΄ μ¦κ° νμκ° ο»Ώ λ₯Ό λμ μ μμ΅λλ€.
Weighted Quick-Unionμ Cost Model
λ°©μ | com[] μ΄κΈ°ν | union | connected (find) |
---|---|---|---|
Weighted Quick-Union | ~N | ~ο»Ώ | ~ ο»Ώ |
rootμ λλ¬νλ μκ° (κΉμ΄ μ ν)μ΄ ο»Ώ μ΄κΈ° λλ¬Έμ μμ κ°μ Costλ₯Ό 보μ λλ€.
Uploaded by N2T