Clone Graph

문제

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

풀이

• 주어진 양방향 그래프를 deep copy하는 문제이다. dfs나 bfs로 인접한 노드를 방문하면서 clone할 수 있다.
• node가 비었을 때 return node나 None 처리가 필요하다.
• bfs 탐색에 필요한 q에 시작값 node를 추가한다.
  • visited가 별도로 필요하지 않은 이유는 answer에 clone graph를 생성하면서 answer에 값이 있는지 확인해주면 되기 때문이다.
• answer의 초기값은 answer[node.val] = Node(node.val, [])
• q가 빌때까지 탐색하면서 now의 neighbors(now와 인접한 노드)를 조회한다.
  • 만약 answer에 neighbors의 원소가 없다면 q에 추가하고 answer[next_node] = Node(next_node.val)로 추가해준다.
• 그리고 answer[now]의 neighbors에도 방금 탐색한 next_node를 추가해주면 된다.

Solution - BFS(Runtime: 43ms)

from typing import Optional
from collections import deque

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return node
        
        q = deque([node])
        answer = {node: Node(node.val)}

        while q:
            now = q.popleft()

            for next_node in now.neighbors:
                if next_node not in answer:
                    q.append(next_node)
                    answer[next_node] = Node(next_node.val)

                answer[now].neighbors.append(answer[next_node])

        return answer[node]

Solution - DFS (Runtime: 46ms)

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return node
            
        answer = {}
            
        def dfs(now):
            if now in answer:  # 이미 존재하는 node라면 return clone graph 
                return answer[now]
                
            clone = Node(now.val)  # 현재 노드
            answer[now] = clone # 그래프에 생성
                
            for next_node in now.neighbors:  # 인접합 노드 탐색
                clone.neighbors.append(dfs(next_node))
                
            return clone 
            
        return dfs(node)

dfs로 풀이한 다른 코드를 참고하였다. leet code에서 이러한 문제가 종종 나오는데.. input output을 테스트하기 어렵다. 개인적으로는 좋은 문제인지 모르겠다.