forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathriver20s.py
More file actions
49 lines (42 loc) ยท 2.04 KB
/
river20s.py
File metadata and controls
49 lines (42 loc) ยท 2.04 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
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
from typing import Optional
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
"""
Time Complexity: O(n + m) (n์ ๋
ธ๋์ ๊ฐ์, m์ ๊ฐ์ ๊ฐ์)
Space Complexity: O(n) (๋
ธ๋ ๊ฐ์๋งํผ ๋งต ์ฌ์ฉ)
"""
# clones_map ๋์
๋๋ฆฌ
# key: ์๋ณธ ๋
ธ๋ ๊ฐ์ฒด
# value: ๋ณต์ ๋
ธ๋ ๊ฐ์ฒด
clones_map = {} # ๋
ธ๋๋ฅผ ๋ณต์ ํ๊ณ ๋ฐ๋ก ๋ฑ๋กํ ๋์
๋๋ฆฌ
def dfs_clone(original_node: Optional['Node']) -> Optional['Node']:
# ์๋ณธ ๋
ธ๋๊ฐ ๋น์ด์์ผ๋ฉด None ๋ฐํ
if not original_node:
return None
# ์๋ณธ ๋
ธ๋๊ฐ clones_map์ ์๋ค๋ฉด
# ์ ์ ๋ณต์ ํ์์ ์๋ฏธ, ํด๋น ๋ณต์ ๋
ธ๋ ๊ฐ์ฒด๋ฅผ ๋ฐํ
if original_node in clones_map:
return clones_map[original_node]
# ์๋ก์ด ๋ณต์ ๋
ธ๋ ์์ฑ ํ val ๋ณต์ฌ
new_clone = Node(original_node.val)
# ์์์ ์์ฑ๋ ๋ณต์ ๋
ธ๋๋ฅผ clones_map์ ๋ฑ๋ก
clones_map[original_node] = new_clone
# ์๋ณธ ๋
ธ๋์ ์ด์์ ๋ณต์ฌ
if original_node.neighbors:
# ๊ฐ๊ฐ์ ์ด์ ๋
ธ๋๋ค์ ๋ํด ์ฒ๋ฆฌ
for original_neighbor in original_node.neighbors:
# ์ฌ๊ท์ ์ผ๋ก dfs_clone ํธ์ถํ์ฌ clone
# (์ ์์
์ ์ํด ์ด๋ฏธ ๋ณต์ ํ๋ค๋ฉด, ๋ณต์ ๋ ๊ฐ์ฒด๊ฐ ๋ฐํ ๋ ๊ฒ)
cloned_neighbor = dfs_clone(original_neighbor)
# ์๋ก ๋ณต์ ๋ ๋
ธ๋ new_clone์ ์ด์์ผ๋ก ์ถ๊ฐ
new_clone.neighbors.append(cloned_neighbor)
return new_clone # ์์ฑ๋ ๋ณต์ ๋
ธ๋ ๋ฐํ
# ์์ ๋
ธ๋๋ก๋ถํฐ ์ฌ๊ท์ ์ธ ๋ณต์ ์์
return dfs_clone(node)