Graphs: 133. Clone Graph

133. Clone Graph

 

이 문제는 연결된 무방향 그래프를 깊은 복사(deep copy)하라는 것입니다. 조금 더 쉽게 설명하자면, 그래프 전체를 복제하라는 것입니다. 그래프는 노드들로 이루어져 있고, 각 노드는 값(val)과 이웃 노드 목록(neighbors)을 가지고 있어요.

핵심 포인트

1. 입력으로 주어진 그래프는 Node로 표현된 연결 그래프입니다.
   • 예를 들어, 노드 1은 Node(1)이고, 이웃 노드가 [2, 4]라면 Node(1).neighbors = [Node(2), Node(4)]와 같은 식으로 표현됩니다.
2. 이웃 노드가 연결된 그래프를 복사할 때, 모든 노드와 이웃 정보를 새로운 그래프로 깊은 복사를 해야 합니다.
   • 단순히 복사하는 것이 아니라, 새로운 메모리에 새로운 노드들을 만들어야 합니다.
3. 그래프의 시작점은 항상 val=1인 노드입니다. 즉, Node(1)에서 시작해 연결된 모든 노드를 복제해야 합니다.

문제를 풀기 위해 필요한 것

1. 깊은 복사란?
   • 깊은 복사는 원본 객체와 완전히 독립적인 새 객체를 만드는 것.
   • 노드가 A → B로 연결되어 있다면, 복사본도 A' → B'로 연결되어야 합니다.
2. DFS/BFS를 이용한 그래프 탐색
   • 그래프는 순환 구조일 수 있으므로, 이미 방문한 노드는 다시 복사하지 않도록 방문 기록을 남겨야 합니다.
   • 이를 위해 딕셔너리(혹은 해시맵)를 사용해 원본 노드와 복사된 노드를 매핑합니다.
3. 반환 값
   • 새로운 그래프의 시작 노드(Node(1)의 복사본)를 반환합니다.

 

풀이 코드 (파이썬)

아래는 DFS를 사용해 그래프를 깊은 복사하는 코드입니다:

 

"""
# 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']:
        # 그래프 문제는 웬만하면 hashmap 으로..
        # dfs 로 품
        # HashMap(old, new)
        if not node:
            return None # 그래프 비워 있으면 

        visited = {} # 원본: 복사본

        def dfs(original_node):
            if original_node in visited:
                return visited[original_node]

            # 현재 노드 복사
            copy = Node(original_node.val)
            visited[original_node] = copy # 복사본 저장

            # 이웃 노드들을 재귀적으로 복사
            for neighbor in original_node.neighbors:
                #copy.neighbors.append(neighbor) # 이렇게 하면 노드가 추가 되는게 아니라 참조됨
                copy.neighbors.append(dfs(neighbor)) # 깊은 복사
            
            return copy

        # copy 노드를 리턴 해야하므로
        return dfs(node)

 

https://youtu.be/mQeF6bN8hMk?si=GhAki4rBvMj_xxfh

 

https://youtu.be/Vszug9Ihnss?si=VhGQquniv6fqAk4C

 

BFS로 풀이

from collections import deque
from typing import Optional

# Definition for a Node.
class Node:
    def __init__(self, val=0, neighbors=None):
        # 노드의 값을 초기화합니다.
        # Initialize the value of the node.
        self.val = val

        # 이웃 노드를 저장하는 리스트를 초기화합니다.
        # Initialize the list of neighboring nodes.
        self.neighbors = neighbors if neighbors is not None else []

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        # 입력 노드가 None인 경우 처리합니다.
        # Handle the case where the input node is None.
        if not node:
            return None

        # BFS 탐색을 위한 큐를 초기화합니다.
        # Initialize the queue for BFS traversal.
        q = deque([node])

        # 복사된 노드를 저장할 딕셔너리를 초기화합니다.
        # Initialize a dictionary to store cloned nodes.
        clon_node = {node: Node(node.val)}  # 시작 노드를 복사합니다.

        while q:
            # 큐에서 현재 노드를 가져옵니다.
            # Dequeue the current node from the queue.
            curr = q.popleft()

            # 현재 노드의 이웃을 순회하며 처리합니다.
            # Iterate over the neighbors of the current node.
            for neighbor in curr.neighbors:
                if neighbor not in clon_node:
                    # 이웃 노드가 복사되지 않은 경우 복사합니다.
                    # Clone the neighbor node if it has not been cloned.
                    clon_node[neighbor] = Node(neighbor.val)

                    # 큐에 이웃 노드를 추가합니다.
                    # Add the neighbor to the queue for BFS.
                    q.append(neighbor)

                # 복사된 노드에 이웃을 추가합니다.
                # Add the cloned neighbor to the current cloned node's neighbors list.
                clon_node[curr].neighbors.append(clon_node[neighbor])

        # 시작 노드의 복사본을 반환합니다.
        # Return the clone of the starting node.
        return clon_node[node]