LeetCode Top Interview 150) Clone Graph

Question

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;
}

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.

# 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']:
        

---

---

Node 클래스끼리 연결된 그래프의 첫번째 노드가 주어지고 해당 노드의 deep_copy한 새로운 트리의 첫번째 노드를 반환하는 문제입니다.

제가 생각한 코드는 다음과 같습니다.

# 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']:
        if not node: 
            return None
        start_num = node.val
        q = deque([node])
        node_dict = {node.val: Node(val=node.val)}
        while q:
            node = q.popleft() 
            copy_node = node_dict[node.val]

            for neighbor in node.neighbors:
                if neighbor.val not in node_dict:
                    node_dict[neighbor.val] = Node(val=neighbor.val)
                    q.append(neighbor)
                    
                copy_node.neighbors.append(node_dict[neighbor.val])
                
        return node_dict[start_num]

• 문제 조건에 의해 node가 없을 수 있으므로 예외처리로 시작합니다.
• start_num : 마지막 반환을 위해 시작노드의 값을 저장합니다.
• q : 그래프 너비탐색을 위한 큐입니다. 깊이탐색을 해도 무방하지만 개인적으로 선호하는 너비탐색으로 골랐습니다.
• node_dict : 노드값 : 카피한 노드 쌍을 저장하는 딕셔너리 입니다. 첫 노드의 복사 노드를 저장합니다. 그래프 탐색을 통해 neighbors를 추가할 예정이기에 초기화는 따로 해주지 않습니다.
• q를 통한 너비 탐색을 시작합니다.
  • 현재 탐색중인 노드 node와 해당 노드의 카피노드 node_dict[node.val]를 불러옵니다.
  • 현재 노드의 이웃노드neighbor를 탐색하며 카피노드에 추가합니다.
    - 만약 이웃노드neighbor가 생성되지 않은 상태라면 생성후 node_dict에 추가합니다.

---

처음에는 딕셔너리를 만들지 않고 그때그때 노드를 만들고 원래 그래프의 너비탐색의 순서에 맞춰 노드를 추가해가려 했습니다.

하지만 비슷한 코드를 반복해서 작성하게되고 neighbors 업데이트를 위해 노드 간 이동이 잦아지기 때문에 가독성이 떨어지는 문제도 있었습니다.

그래서 필요한 노드를 바로바로 불러오고 확인해볼수 있도록 딕셔너리 형태로 저장해두면서 불러왔습니다.

효율에만 신경쓰다가 한바퀴 돌고 푼 느낌이 있어서 앞으로는 생각나는 무식한 방법을 적용하고 개선점을 확인하는 방향으로도 고려하는게 좋을것 같다는 생각이 듭니다.