forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtaurus09318976.py
More file actions
79 lines (62 loc) ยท 2.9 KB
/
taurus09318976.py
File metadata and controls
79 lines (62 loc) ยท 2.9 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
"""
๋ฌธ์ ์ ํต์ฌ ํฌ์ธํธ:
๊ฐ ๋
ธ๋๋ ๊ฐ๊ณผ ์ด์ ๋
ธ๋๋ค์ ๋ฆฌ์คํธ๋ฅผ ๊ฐ์ง
์๋ณธ ๊ทธ๋ํ์ ์์ ํ ๋
๋ฆฝ์ ์ธ ์๋ก์ด ๊ทธ๋ํ ์์ฑ
๋ชจ๋ ์ฐ๊ฒฐ ๊ด๊ณ๋ฅผ ๊ทธ๋๋ก ๋ณต์ฌ
ํด๊ฒฐ ๋ฐฉ๋ฒ:
DFS(๊น์ด ์ฐ์ ํ์) + ํด์๋งต์ ์ฌ์ฉํจ:
ํด์๋งต์ผ๋ก ์๋ณธ ๋
ธ๋์ ๋ณต์ฌ๋ณธ ๋
ธ๋์ ๋งคํ ๊ด๊ณ ์ ์ฅ
DFS๋ก ๊ทธ๋ํ๋ฅผ ์ํํ๋ฉด์ ๊ฐ ๋
ธ๋๋ฅผ ๋ณต์ฌ
์ด๋ฏธ ๋ณต์ฌ๋ ๋
ธ๋๋ ํด์๋งต์์ ์ฐพ์์ ์ฌ์ฌ์ฉ
Example 1์ ๊ฒฝ์ฐ
1 --- 2
| |
| |
4 --- 3
์คํ ๊ณผ์ :
๋
ธ๋ 1 ๋ณต์ฌ: clone_1 ์์ฑ, visited = clone_1
๋
ธ๋ 1์ ์ด์ 2 ๋ณต์ฌ: clone_2 ์์ฑ, visited = clone_2
๋
ธ๋ 2์ ์ด์ 1 ์ฒ๋ฆฌ: ์ด๋ฏธ visited์ ์์ผ๋ฏ๋ก clone_1 ๋ฐํ
๋
ธ๋ 2์ ์ด์ 3 ๋ณต์ฌ: clone_3 ์์ฑ, visited = clone_3
๋
ธ๋ 3์ ์ด์๋ค ์ฒ๋ฆฌ: clone_2, clone_4 ์ฐ๊ฒฐ
๋
ธ๋ 1์ ์ด์ 4 ๋ณต์ฌ: clone_4 ์์ฑ, visited = clone_4
๋ชจ๋ ์ฐ๊ฒฐ ๊ด๊ณ ์์ฑ
Output: ์๋ณธ๊ณผ ๋์ผํ ๊ตฌ์กฐ์ ์์ ํ ์๋ก์ด ๊ทธ๋ํ
์๊ฐ ๋ณต์ก๋: O(V + E)
V: ๋
ธ๋(์ ์ )์ ๊ฐ์, E: ๊ฐ์ ์ ๊ฐ์
๊ฐ ๋
ธ๋๋ฅผ ํ ๋ฒ์ฉ ๋ฐฉ๋ฌธํ๊ณ , ๊ฐ ๊ฐ์ ์ ํ ๋ฒ์ฉ ์ฒ๋ฆฌ
DFS์ ํ์ค ์๊ฐ ๋ณต์ก๋
๊ณต๊ฐ ๋ณต์ก๋: O(V)
visited ํด์๋งต์ด ๋ชจ๋ ๋
ธ๋๋ฅผ ์ ์ฅ: O(V)
DFS ์ฌ๊ท ํธ์ถ ์คํ์ ์ต๋ ๊น์ด: O(V)
๋ณต์ฌ๋ ๊ทธ๋ํ ์์ฒด๋ O(V + E)์ ๊ณต๊ฐ ํ์
"""
from typing import Optional
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
# ๋น ๊ทธ๋ํ์ธ ๊ฒฝ์ฐ None ๋ฐํ
if not node:
return None
# ์๋ณธ ๋
ธ๋๋ฅผ ํค๋ก, ๋ณต์ฌ๋ณธ ๋
ธ๋๋ฅผ ๊ฐ์ผ๋ก ํ๋ ํด์๋งต ์์ฑ
# ์ค๋ณต ๋ณต์ฌ๋ฅผ ๋ฐฉ์งํ๊ณ ์ํ ์ฐธ์กฐ ๋ฌธ์ ํด๊ฒฐ
visited = {}
# DFS ํจ์ ์ ์
def dfs(original_node):
# ์ด๋ฏธ ๋ณต์ฌ๋ ๋
ธ๋๋ผ๋ฉด ๊ธฐ์กด ๋ณต์ฌ๋ณธ์ ๋ฐํ (์ค๋ณต ๋ณต์ฌ ๋ฐฉ์ง)
if original_node in visited:
return visited[original_node]
# ์๋ณธ ๋
ธ๋์ ๊ฐ์ผ๋ก ์๋ก์ด ๋
ธ๋ ์์ฑ
# ์ด์ ๋ฆฌ์คํธ๋ ๋น ๋ฆฌ์คํธ๋ก ์ด๊ธฐํ
clone_node = Node(original_node.val, [])
# ํด์๋งต์ ์๋ณธ-๋ณต์ฌ๋ณธ ๋งคํ ๊ด๊ณ ์ ์ฅ
# ์ํ ์ฐธ์กฐ ๋ฐฉ์ง๋ฅผ ์ํด ์ด์์ ์ฒ๋ฆฌํ๊ธฐ ์ ์ ๋จผ์ ์ ์ฅ
visited[original_node] = clone_node
# ์๋ณธ ๋
ธ๋์ ๋ชจ๋ ์ด์๋ค์ ์ฌ๊ท์ ์ผ๋ก ๋ณต์ฌ
# ๋ณต์ฌ๋ ์ด์ ๋
ธ๋๋ค์ ํ์ฌ ๋ณต์ฌ๋ณธ์ ์ด์ ๋ฆฌ์คํธ์ ์ถ๊ฐ
for neighbor in original_node.neighbors:
# ์ด์ ๋
ธ๋๋ฅผ ๋ณต์ฌํ๊ณ ํ์ฌ ๋
ธ๋์ ์ด์ ๋ฆฌ์คํธ์ ์ถ๊ฐ
clone_node.neighbors.append(dfs(neighbor))
# ์์ฑ๋ ๋ณต์ฌ๋ณธ ๋
ธ๋ ๋ฐํ
return clone_node
# ์ฃผ์ด์ง ๋
ธ๋๋ถํฐ DFS ์์
return dfs(node)