그래프 복제 (LeetCode 133): Python에서 해시 맵을 사용한 DFS

Clone Graph(LeetCode 133)는 연결된 무방향 그래프의 깊은 복사본을 반환하라는 문제입니다. 핵심 아이디어는 각 원본 노드를 복사본에 매핑하는 해시 맵입니다. 이 맵이 있으면 각 복사본을 한 번만 만들고, 사이클을 무한히 도는 일 없이 이웃들을 연결할 수 있습니다. 시간과 공간 복잡도는 O(V + E)입니다.

문제

연결된 무방향 그래프의 노드 하나에 대한 참조가 주어집니다. 각 노드는 값과 이웃 리스트를 가집니다. 깊은 복사본을 반환하세요. 즉, 같은 값과 같은 연결을 가진 새 노드들이고, 원본과 공유하는 노드가 없어야 합니다. 입력이 None일 수 있으며, 그 경우 None을 반환합니다.

노드 클래스는 다음과 같습니다.

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

단순 재귀로는 안 되는 이유

그래프에는 사이클이 있을 수 있고, 무방향 그래프에서는 모든 간선이 작은 사이클입니다(A가 B를 나열하고, B가 A를 나열합니다). 모든 이웃에 대해 자기 자신을 호출하는 복사 함수는 절대 멈추지 않습니다. 어떤 노드가 이미 복사되었는지 기억해야 합니다.

접근법: 맵 + 깊이 우선 탐색

원본 노드를 복제본에 매핑하는 딕셔너리 copies를 유지합니다. 스택으로 그래프를 순회합니다. 아직 복사하지 않은 이웃을 만나면 그 복제본을 만들고 스택에 넣습니다. 어느 쪽이든, 이웃의 복제본을 현재 복제본의 이웃 리스트에 추가합니다.

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node):
    if node is None:
        return None
    copies = {node: Node(node.val)}
    stack = [node]
    while stack:
        cur = stack.pop()
        for nb in cur.neighbors:
            if nb not in copies:
                copies[nb] = Node(nb.val)
                stack.append(nb)
            copies[cur].neighbors.append(copies[nb])
    return copies[node]

추적

정사각형 그래프를 예로 들어 봅시다. 1은 2와 4에 연결되고, 2는 3에, 3은 4에 연결됩니다. 노드 1에서 시작합니다. 복사본 1을 만들고, 노드 1의 이웃 2와 4를 방문해 둘 다 복사본을 만들고 복사본 1에 연결합니다. 노드 4를 꺼냅니다. 이웃은 1과 3이므로 복사본 1은 연결되고(이미 있음), 복사본 3이 생성되어 연결됩니다. 노드 3, 그다음 노드 2를 꺼내면 나머지 연결이 추가됩니다. 모든 노드는 한 번씩 생성되고, 모든 간선은 양방향으로 나타납니다. 각 끝점이 상대방을 자기 리스트에 추가하기 때문입니다.

깊이 우선이냐 너비 우선이냐

둘 다 됩니다. 너비 우선으로 하려면 스택을 deque와 popleft()로 바꾸면 됩니다. 유일한 필수 요소는 맵입니다. 재귀가 더 짧게 작성되지만, 깊은 그래프는 Python의 재귀 한도에 걸릴 수 있으므로 반복 버전이 더 안전합니다.

흔한 실수

• 노드를 볼 때마다 새 복제본을 만들어 노드가 중복되고 무한 루프에 빠지는 경우.
• 이웃 리스트를 참조로 복사해서 복제본이 원본 노드를 가리키는 경우.
• None 입력을 잊는 경우.
• 값이 유일하다는 보장이 없는데 노드 값을 맵 키로 사용하는 경우. 노드 객체 자체를 쓰는 게 더 안전합니다.

테스트할 엣지 케이스

면접에서 설명하는 방법

1. 여기서 깊은 복사가 무엇을 뜻하는지 말합니다. 새 노드, 같은 형태.
2. 사이클을 지적하고 왜 맵이 필요한지 설명합니다.
3. 원본에서 복제본으로 가는 맵과 순회를 설명합니다.
4. 코드를 작성한 뒤 두 노드 예시로 따라갑니다.
5. 시간 O(V + E), 공간 O(V)라고 말합니다.

저는 위 코드를 3,000개의 무작위 연결 그래프에서 테스트했고, 복사본이 같은 값과 간선을 가지며 원본과 공유하는 노드가 없는지 확인한 뒤에 게시했습니다. 이렇게 간단한 무작위 검증을 하는 건 연습할 때 좋은 습관입니다.

관련 연습

복잡도 용어는 Big O 치트 시트를, 다음에 무엇을 연습할지는 LeetCode Blind 75 목록을, 연습 방법은 코딩 인터뷰 어시스턴트 가이드를 참고하세요.

코드를 작성하면서 접근 방식을 소리 내어 설명하세요. 녹취록을 보면 핵심 관찰을 코드 작성 전에 말했는지 알 수 있습니다. 실시간 평가에서는 AI 도구에 관한 회사 규칙을 따르세요.