LeetCode 133 - Clone Graph

연결된 무방향 그래프의 한 노드가 주어졌을 때, 그래프 전체를 동일한 구조와 값을 갖는 새로운 노드들로 깊은 복사(Deep Copy)하는 Medium 문제다. 이미 복제된 노드를 해시맵에 기록하여 무한 루프를 방지하고, DFS 재귀 호출을 통해 인접 노드들을 순차적으로 복제하여 연결했다.

문제 링크 & 설명

문제 링크: 133. Clone Graph
요약: 무방향 그래프의 임의의 노드 참조가 주어질 때, 원래 노드들을 참조하지 않는 완전히 독립된 복제본 그래프를 생성하고 그 시작 노드를 반환한다.

그래프는 사이클(순환 참조)을 포함할 수 있으므로, 단순 탐색을 진행하면 이미 방문한 노드를 다시 복제하려고 시도하다가 재귀가 끝나지 않는다. 따라서 원본 노드와 새로 생성한 복제 노드를 1:1로 매핑해두는 캐싱 구조가 필수적이다.

접근 방법

cloned 딕셔너리를 두어 원본 노드: 복제 노드 쌍을 저장한다.

cloned = {}

def dfs(curr):
    if curr in cloned:
        return cloned[curr]

    copy = Node(curr.val)
    cloned[curr] = copy

    for neighbor in curr.neighbors:
        copy.neighbors.append(dfs(neighbor))

    return copy

기저 조건(방문 여부 확인): 현재 탐색 중인 노드 curr가 이미 cloned에 존재한다면 추가 복제 없이 기존 복제 노드 cloned[curr]를 즉시 반환한다.
복제 노드 생성 및 등록: 아직 복제되지 않은 노드라면 Node(curr.val)로 새 노드를 생성하고, 인접 노드를 탐색하기 전에 먼저 cloned에 등록한다. 인접 노드 복제 중에 다시 자기 자신을 참조하더라도 사이클에 빠지지 않게 하기 위함이다.
인접 리스트 구성: 원본 노드의 neighbors를 순회하며 각각 dfs(neighbor)를 호출해 반환된 복제 노드를 copy.neighbors에 추가한다.

복잡도 분석

시간 복잡도: O(V + E)
- 그래프의 모든 정점(V)과 간선(E)을 정확히 한 번씩만 방문한다.
공간 복잡도: O(V)
- 모든 정점을 해시맵 cloned에 보관하며, 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']:
        if not node:
            return None

        cloned = {}

        def dfs(curr):
            if curr in cloned:
                return cloned[curr]

            copy = Node(curr.val)
            cloned[curr] = copy

            for neighbor in curr.neighbors:
                copy.neighbors.append(dfs(neighbor))

            return copy

        return dfs(node)

요약 및 회고

그래프의 깊은 복사에서 핵심은 순환 참조를 끊어내는 것이다. 새 노드를 만들자마자 인접 노드를 재귀 탐색하기 전에 해시맵에 먼저 등록하는 순서가 중요한데, 이 순서가 보장되어야 상호 참조 관계가 있는 이웃 노드들이 서로를 계속해서 호출하는 무한 재귀를 막을 수 있다.