Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Example 3:
Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
Constraints:
The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.
✔ 문제접근 #1 DFS재귀[통과] ⭕
Intuition 각 노드는 인접한 노드들을 가지고 있기 때문에 DFS탐색을 통하여 새로운 노드를 생성해준다.
Algorithm
시작점 node부터 dfs탐색을 수행한다.
dfs는 새로운 clone노드를 생성하고, node의 인접한 노드들에 dfs(node의 인접한 다음노드)로 구한 새로운 하위 노드를 추가해주면서 재귀적으로 탐색한다.
from typing import Optional
class Solution:
def dfs(self, node, visited):
if node in visited:
return visited[node]
clone = Node(node.val)
visited[node] = clone
for next_node in node.neighbors:
clone.neighbors.append(self.dfs(next_node, visited))
return clone
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if node == None:
return node
visited = {}
return self.dfs(node, visited)
Complexity Analysis
시간 복잡도 : O(N)
N개의 노드탐색 O(M)
그러므로 전체시작복잡도 : O(N)
공간복잡도 : O(N)
노드의 개수만큼 새로운 clone노드들을 복사한다.
기타풀이 및 회고
탐색하는 기본적인 문제였고, DFS 혹은 BFS방식으로 많이 해결 한 것 같다. 문제조건에서 Node.val값이 유일하기 때문에 방문처리에 필요한 visited 딕셔너리의 key값으로 활용할 수 있었다.
자주 사용하는 방식인 인접리스트에 값이 들어가있는 방식이 아닌 인접리스트에 class형식의 노드가 들어가 있기 때문에 새로운 Node 클래스를 생성해주고 인접리스트에 추가해주는 방식만 주의해주면 된다.
