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]

 

"""
# 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']:
        # 입력 노드가 None인 경우 처리
        if not node:
            return None

        # 큐와 복사된 노드를 저장할 딕셔너리 초기화
        q = deque([node])
        clon_node = {node: Node(node.val)}  # 시작 노드 복사    

        while q:
            curr = q.popleft()

            # 현재 노드의 이웃을 순회하며 처리
            for neighbor in curr.neighbors:
                if neighbor not in clon_node:
                    # 이웃 노드가 복사되지 않은 경우 복사
                    clon_node[neighbor] = Node(neighbor.val)
                    q.append(neighbor)
                
                # 복사된 노드에 이웃 추가

                clon_node[curr].neighbors.append(clon_node[neighbor])

        return clon_node[node]

 

최종 코드

 

좋아요! 이 문제는 무방향 그래프를 깊은 복사(deep copy) 하는 문제고,
인접 리스트 방식으로 주어지는 그래프를 DFS 또는 BFS로 탐색하면서
각 노드를 복사하고 서로 연결 관계까지 그대로 유지해줘야 합니다.

---

✅ 핵심 아이디어:

• 원래 노드가 Node(val, neighbors) 형태로 주어짐
• 각 노드를 복사하면서, 이웃들도 재귀적으로 복사
• 이미 복사한 노드는 딕셔너리(해시맵)로 추적해서 중복 복사 방지

# 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']:
        # 그래프가 비어있으면 None 리턴
        if not node:
            return None

        # 복사된 노드를 저장할 딕셔너리: {원래 노드: 복사된 노드}
        cloned = {}

        # DFS 함수 정의
        def dfs(curr):
            # 이미 복사한 노드라면, 저장된 복사 노드 리턴
            if curr in cloned:
                return cloned[curr] 

            # 현재 노드 복사본 생성
            copy = Node(curr.val)
            # 복사본을 cloned 딕셔너리에 저장 (순환 방지 및 재사용 목적)
            cloned[curr] = copy

            # 현재 노드의 이웃들을 순회하며
            for n in curr.neighbors:
                # 이웃도 복사해서, 복사본 노드의 이웃 리스트에 추가
                copy.neighbors.append(dfs(n))  

            # 복사 완료된 노드 리턴
            return copy

        # DFS 시작 (node가 시작 노드)
        return dfs(node)

 

🧠 정리하면:

• cloned 딕셔너리는 순환 구조에서 무한 루프 방지 역할
• dfs(n)을 통해 이웃도 깊은 복사 수행
• 원래 그래프의 구조와 완전히 동일한 새로운 그래프가 생성됨