forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKwonNayeon.py
More file actions
46 lines (36 loc) · 1.14 KB
/
KwonNayeon.py
File metadata and controls
46 lines (36 loc) · 1.14 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
"""
Valid Tree의 조건:
1. 모든 노드가 연결되어 있어야 함
2. 사이클이 없어야 함
3. edge의 개수는 n-1개
Time Complexity: O(V + E)
- V: 노드의 개수
- E: edge의 개수
Space Complexity: O(V)
- 노드 방문 여부를 저장하는 visited set 사용
풀이방법:
1. 기본 조건 체크: edge의 개수는 n-1개
2. 각 노드별로 연결된 노드들의 정보를 저장
- 무방향 그래프이므로 양쪽 모두 저장
3. DFS로 노드 탐색
- 0번 노드부터 시작해서 연결된 모든 노드를 방문
- 이미 방문한 노드는 재방문하지 않음
4. 모든 노드 방문 확인
- visited의 크기가 n과 같다면 모든 노드가 연결된 것 -> valid tree
"""
def validTree(n, edges):
if len(edges) != n - 1:
return False
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
visited = set()
def dfs(node):
if node in visited:
return
visited.add(node)
for next_node in adj[node]:
dfs(next_node)
dfs(0)
return len(visited) == n