forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhaklee.py
More file actions
160 lines (122 loc) Β· 6.13 KB
/
haklee.py
File metadata and controls
160 lines (122 loc) Β· 6.13 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
"""
μμ΄λμ΄:
- νΈλ¦¬μ¬μΌ νλ―λ‘ μ£μ§ κ°μκ° n-1κ°μ¬μΌ νλ€.
- μ£μ§ κ°μκ° n-1κ°μ΄λ―λ‘ λ§μ½ μ€κ°μ μ¬μ΄ν΄μ΄ μλ€λ©΄ νΈλ¦¬κ° μ°κ²°μ΄ μ λλ€.
- μ°κ²°μ΄ μ λμμΌλ νΈλ¦¬λ μλκ³ ... λͺ μ‘°κ°μΌλ‘ μͺΌκ°μ§ κ·Έλνκ° λλ€. μ¬νΌ, valid treeκ°
μλκ² λλ€.
- spanning tree λ§λ€ λλ₯Ό μκ°ν΄λ³΄μ. μ£μ§ νλλ₯Ό λν λλ§λ€ λ
Έλκ° νλμ© νΈλ¦¬μ μΆκ°λμ΄μΌ
μ£μ§ n-1κ°λ‘ λ
Έλ nκ°λ₯Ό κ²¨μ° λ§λ€ μ μλλ°, μ€κ°μ μλ‘μ΄ λ
Έλλ₯Ό μΆκ° μνκ³ μν κ³³μ
μ£μ§λ₯Ό μ¨μ μ¬μ΄ν΄μ λ§λ€κ±°λ νλ©΄ λͺ¨λ λ
Έλλ₯Ό μ°κ²°ν λ°©λ²μ΄ μλ€.
- μμ μμλ³΄λ€ μ’ λ μΌλ°μ μΌλ‘λ union-find μκ³ λ¦¬μ¦μμ μ€λͺ
νλ union μνμΌλ‘λ μ€λͺ
μ΄
κ°λ₯νλ€. union-findμμλ μ²μμ nκ°μ λ
Έλλ€μ parentκ° μκΈ° μμ μΌλ‘ μΈν
λμ΄ μλλ°,
μ¦, λͺ¨λ λ
Έλλ€μ΄ nκ°μ κ·Έλ£ΉμΌλ‘ λλμ΄μλλ°, μ¬κΈ°μ unionμ ν λ² μνν λλ§λ€ κ·Έλ£Ήμ΄ 1κ°
νΉμ 0κ° μ€μ΄λ€ μ μλ€. κ·Έλ°λ° μ λ¬Έμ μμλ unionμ μ£μ§ κ°μ λ§νΌ, μ¦, n-1ν μνν μ μμΌλ―λ‘,
λ§μ½ union μνμμ κ·Έλ£Ήμ κ°μκ° μ€μ΄λ€μ§ μλ κ²½μ°(μ¦, μ£μ§ μ°κ²°μ ν΅ν΄ μ¬μ΄ν΄μ΄ μκΈΈ κ²½μ°)κ°
ν λ²μ΄λΌλ λ°μνλ©΄ union μν ν κ·Έλ£Ήμ κ°μκ° 2 μ΄μμ΄ λμ΄ λ
Έλλ€μ΄ μλ‘ μ°κ²°λμ§ μμ νΈλ¦¬λ₯Ό
μ΄λ£¨μ§ λͺ»νλ€.
"""
"""TC: O(n * Ξ±(n)), SC: O(n)
nμ μ£Όμ΄μ§ λ
Έλμ κ°μ, eλ μ£Όμ΄μ§ μ£μ§μ κ°μ.
μμ΄λμ΄(μ΄μ΄μ):
- union-find μμ΄λμ΄λ₯Ό κ·Έλλ‘ νμ©νλ€.
- λμ΄λΈν μ κ·Ό:
- unionμ ν΅ν΄μ μ£μ§λ‘ μ°κ²°λ λ μ§ν©μ ν©μΉλ€.
- findλ₯Ό ν΅ν΄μ 0λ²μ§Έ λ
Έλμ λͺ¨λ λ
Έλλ€μ΄ κ°μ μ§ν©μ μν΄μλμ§ νμΈνλ€.
- λ μ’μ ꡬν:
- union μν μ€ κ°μ μ§ν©μ μν λ λ
Έλλ₯Ό ν©μΉλ €κ³ νλ κ²μ λ°κ²¬νλ©΄ False 리ν΄
- union-findλ [Disjoint-set data structure - Wikipedia](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)
λ₯Ό κΈ°λ°μΌλ‘ ꡬννλ€. μ¬κΈ°μ time complexity κ΄λ ¨ μ€λͺ
μ΄ μμΈνκ² λμ€λλ° κΆκΈνλ©΄ μ°Έκ³ .
SC:
- union-findμμ μΈ parent μ λ³΄λ§ κ΄λ¦¬νλ€. κ° λ
Έλλ§λ€ parent λ
Έλ(μΈλ±μ€), rankλ₯Ό κ΄λ¦¬νλ―λ‘ O(n).
TC:
- union κ³Όμ μ union by rank μ μ©μ O(Ξ±(n)) λ§νΌμ μκ°μ΄ λ λ€. μ΄λ Ξ±(n)μ inverse Ackermann function
μΌλ‘, λ§€μ° λλ¦° μλλ‘ λμ΄λλ―λ‘ μ¬μ€μ μμλΌκ³ λ΄λ 무방νλ€.
- union μνμ μ΅λ eλ² μ§ννλ―λ‘ O(e * Ξ±(n)).
- e = n-1 μ΄λ―λ‘ O(n * Ξ±(n)).
"""
class Solution:
"""
@param n: An integer
@param edges: a list of undirected edges
@return: true if it's a valid tree, or false
"""
def valid_tree(self, n, edges):
# write your code here
# union find
parent = list(range(n))
rank = [0] * n
def find(x: int) -> bool:
if x == parent[x]:
return x
parent[x] = find(parent[x]) # path-compression
return parent[x]
def union(a: int, b: int) -> bool:
# μλλ κ°μ 리ν΄νμ§ μμλ λμ§λ§, κ°μ μ§ν©μ μν λ
Έλλ₯Ό
# unionνλ €λ μν©μ νλ³νκΈ° μν΄ κ° λ¦¬ν΄.
pa = find(a)
pb = find(b)
# union by rank
if pa == pb:
# parentκ° κ°μ. rank μμ
μ ν΄λ λλ€.
return True
if rank[pa] < rank[pb]:
pa, pb = pb, pa
parent[pb] = pa
if rank[pa] == rank[pb]:
rank[pa] += 1
return False
if len(edges) != n - 1:
# νΈλ¦¬μλ μ£μ§κ° `(λ
Έλ κ°μ) - 1`κ° λ§νΌ μλ€.
# μ΄ μ‘°κ±΄ λ§μ‘± μνλ©΄ 컀ν
.
return False
# λμ΄λΈν ꡬν:
# - λͺ¨λ μ£μ§λ‘ union μν
# - findλ‘ λͺ¨λ λ
Έλκ° 0λ² λ
Έλμ κ°μ μ§ν©μ μν΄μλμ§ νμΈ
# for e in edges:
# union(*e)
# return all(find(0) == find(i) for i in range(n))
# λ μ’μ ꡬν:
# - union μν μ€ κ°μ μ§ν©μ μν λ λ
Έλλ₯Ό ν©μΉλ €κ³ νλ κ²μ λ°κ²¬νλ©΄ False 리ν΄
for e in edges:
if union(*e):
return False
return True
"""TC: O(n), SC: O(n)
nμ μ£Όμ΄μ§ λ
Έλμ κ°μ, eλ μ£Όμ΄μ§ μ£μ§μ κ°μ.
μμ΄λμ΄(μ΄μ΄μ):
- νΈλ¦¬λ₯Ό μ μ΄λ€λμ§ νμΈνλ €λ©΄ ν λ
Έλμμ μμν΄μ dfsλ₯Ό λλ €μ λͺ¨λ λ
Έλλ€μ λλ¬ κ°λ₯νμ§
체ν¬νλ©΄ λλλ°, μ΄κ² μκ°λ³΅μ‘λμ λ μ 리νμ§ μμκΉ?
SC:
- adjacency listλ₯Ό κ΄λ¦¬νλ€. O(e).
- νΈμΆ μ€νμ νμμ μμνλ λ
Έλλ‘λΆν° μ¬μ΄ν΄μ΄ λμ€μ§ μλ κ²½λ‘μ μ΅λ κΈΈμ΄λ§νΌ κΉμ΄μ§ μ μλ€.
μ΅μ
μ κ²½μ° O(n).
- μ΄λ e = n-1 μ΄λ―λ‘ μ’
ν©νλ©΄ O(n).
TC:
- κ° λ
Έλμ μ κ·Όνλ κ³Όμ μ O(1). μ΄λ° λ
Έλλ₯Ό μ΅μ
μ κ²½μ° nκ° μ κ·Όν΄μΌ νλ―λ‘ O(n).
"""
class Solution:
"""
@param n: An integer
@param edges: a list of undirected edges
@return: true if it's a valid tree, or false
"""
def valid_tree(self, n, edges):
# write your code here
if len(edges) != n - 1:
# νΈλ¦¬μλ μ£μ§κ° `(λ
Έλ κ°μ) - 1`κ° λ§νΌ μλ€.
# μ΄ μ‘°κ±΄ λ§μ‘± μνλ©΄ 컀ν
.
return False
adj_list = [[] for _ in range(n)]
for a, b in edges:
adj_list[a].append(b)
adj_list[b].append(a)
visited = [False for _ in range(n)]
def dfs(node):
visited[node] = True
for adj in adj_list[node]:
if not visited[adj]:
dfs(adj)
# ν λ
Έλμμ μΆλ°ν΄μ λͺ¨λ λ
Έλκ° visted λμ΄μΌ μ£Όμ΄μ§ μ£μ§λ€λ‘ νΈλ¦¬λ₯Ό λ§λ€ μ μλ€.
# μ무 λ
Έλμμλ μΆλ°ν΄λ λλλ° 0λ²μ§Έ λ
Έλλ₯Ό μ ννμ.
dfs(0)
return all(visited)