LeetCode 133 Clone Graph 풀이: 방문 매핑을 사용하는 그래프 DFS

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

• 문제: 133. Clone Graph
• 출처: LeetCode
• 학습: 그래프 학습 가이드
• 자체 판단 난이도: Level 3

그래프의 시작 노드를 받아 전체 그래프를 깊은 복사해야 한다. 그래프를 순회하면서 방문 매핑으로 각 원본 노드를 정확히 한 번만 복제해야 한다. 그래프와 깊은 복사에 대한 이해가 필요하여 Level 3으로 판단했다.

1. 문제 요약

각 노드는 정수 값과 이웃 노드를 가지고 있다. 주어진 노드에서 도달할 수 있는 모든 노드를 새로 만들고, 새 노드끼리 원본과 같은 관계를 구성해야 한다.

원본 노드를 그대로 이웃 목록에 넣으면 얕은 복사가 되므로, 원본 그래프와 복제 그래프의 노드는 서로 다른 객체여야 한다. 입력 그래프는 연결된 무방향 그래프이며, 빈 그래프인 경우에는 None을 반환한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그래프 구조와 방문 기록

그래프를 순회하면서 다음 매핑을 유지하면 복사와 방문 처리를 동시에 해결할 수 있다.

원본 노드 객체 → 복제 노드 객체

처음 만난 원본 노드는 즉시 복제해 저장한 뒤 이웃을 탐색한다. 이후 순환이나 다른 경로를 통해 같은 원본 노드를 다시 만나면 새 객체를 만들지 않고 매핑된 복제 노드를 사용한다. 재귀 호출 전에 저장하는 순서가 중요하다.

DFS 순서

1. 입력 노드가 None이면 None을 반환한다.
2. 이미 복제한 원본 노드라면 저장된 복제 노드를 반환한다.
3. 현재 노드의 복제본을 만들고 즉시 매핑에 저장한다.
4. 원본 이웃을 DFS로 복제해 현재 복제본의 이웃 목록에 추가한다.

원본-복제 대응 불변식

DFS가 반환될 때마다 매핑에 등록된 원본 노드는 정확히 하나의 복제 노드와 대응하고, 그때까지 확인한 이웃은 복제 노드의 이웃으로 같은 순서로 연결되어 있어야 한다. 노드를 만들자마자 매핑하는 것은 이 불변식을 재귀 중에도 유지하는 장치다. 따라서 자기 자신으로 돌아오는 간선이나 여러 경로로 들어오는 간선도 같은 복제 객체를 가리키며, 원본 객체가 복제 그래프에 섞이지 않는다.

3. 문제 해결 코드 (Python)

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node is None:
            return None

        clones = {}

        def clone(current):
            if current in clones:
                return clones[current]

            copied = Node(current.val)
            clones[current] = copied

            for neighbor in current.neighbors:
                copied.neighbors.append(clone(neighbor))

            return copied

        return clone(node)

각 노드와 간선을 한 번씩 확인하므로 시간 복잡도는 O(V + E)다. V는 노드 수, E는 간선 수다. 매핑과 DFS 호출 스택에 O(V) 공간을 사용한다.

4. 오답 접근과 반례

방문 매핑 없이 이웃을 따라가며 매번 새 노드를 만들면 순환 그래프에서 무한 재귀가 발생한다. 예를 들어 1 - 2 - 3 - 1 구조에서 1을 복제한 뒤 2, 3을 따라가면 다시 1을 만나게 되므로, 이미 복제한 1을 재사용해야 한다.

복제 노드를 매핑에 저장하기 전에 이웃을 재귀 호출하면 자기 자신으로 돌아오는 간선을 처리할 때 매핑이 비어 있다. 반드시 copied를 만든 직후 clones[current] = copied를 먼저 실행해야 한다.

복사해 실행할 테스트

로컬 실행 시 아래 Node 보조 클래스를 풀이 코드보다 먼저 두고 assert를 뒤에 붙인다. 순환 간선에서 복제 매핑이 재사용되는지도 검사한다.

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors or []

a, b = Node(1), Node(2)
a.neighbors = [b]
b.neighbors = [a]
clone = Solution().cloneGraph(a)
assert clone is not a and clone.val == 1
assert clone.neighbors[0] is not b
assert clone.neighbors[0].neighbors[0] is clone

5. 공식 예제와 추가 검증

LeetCode 공식 예제 3개를 Python 3.12.4에서 Node 테스트 클래스로 재현해 검증했다.

추가 검증 1: 단순한 두 노드 연결

입력: 1 - 2
기대 결과: 값과 양방향 연결이 같고 두 노드 객체는 원본과 다름
확인 결과: 통과
검증 목적: 기본 복제와 객체 분리 확인

추가 검증 2: 삼각형 순환

입력: 1 - 2 - 3 - 1
기대 결과: 세 노드와 세 개의 양방향 간선을 유지한 새 그래프
확인 결과: 통과
검증 목적: 순환에서 매핑 재사용 및 무한 재귀 방지 확인

추가 검증 3: 원본과 복제의 독립성

입력: 1 - 2
검증: 복제된 1의 neighbors를 변경
기대 결과: 원본 1의 neighbors는 변경되지 않음
확인 결과: 통과
검증 목적: 얕은 복사가 아닌 깊은 복사 확인

6. 참고 풀이 비교

• Clone Graph 공식 문제는 연결된 무방향 그래프와 깊은 복사 조건을 정의한다.
• AlgoMonster의 설명은 DFS로 그래프를 순회하면서 원본과 복제 노드를 매핑하는 접근을 설명한다.

BFS를 사용해도 같은 매핑을 유지하면 O(V + E) 시간과 O(V) 공간으로 해결할 수 있다. 이 글에서는 재귀 구조가 복제 과정을 자연스럽게 보여주는 DFS를 선택했으며, 노드 수가 매우 커져 재귀 깊이가 걱정된다면 큐를 사용하는 BFS로 바꿀 수 있다.

마무리

Clone Graph의 핵심은 그래프를 방문하는 것보다 원본 노드와 복제 노드의 관계를 기억하는 것이다. 복제 노드를 먼저 매핑한 뒤 이웃을 연결하면 순환 그래프에서도 각 노드를 한 번만 만들고 원본과 독립적인 깊은 복사본을 구성할 수 있다.

관련 문제

• Surrounded Regions 풀이