FilesExpand file tree

 main

/

river20s.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

49 lines (42 loc) · 2.04 KB

 main

/

river20s.py

Top

File metadata and controls

• Code
• Blame

49 lines (42 loc) · 2.04 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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)