a-081-clone-graph2026-08-08mediumleetcode #133neetcode150

그래프 복제

#hash-table#depth-first-search#breadth-first-search#graph

문제

· problem

P.a-081-clone-graph

그래프 복제

연결된 무방향 그래프의 한 노드에 대한 참조가 주어집니다. 그래프의 깊은 복제(deep copy, clone)를 반환하세요. 그래프의 각 노드는 정수 값(int)과 이웃 노드들의 리스트(List[Node])를 포함합니다. class Node { public int val; public List<Node> neighbors; } 테스트 케이스 형식: 편의상 각 노드의 값은 해당 노드의 인덱스(1-indexed)와 같습니다. 예를 들어 첫 번째 노드는 val == 1, 두 번째 노드는 val == 2 등입니다. 그래프는 인접 리스트(adjacency list)를 사용하여 표현됩니다. 인접 리스트는 유한 그래프를 나타내기 위해 사용되는 순서 없는 리스트들의 모음입니다. 각 리스트는 그래프의 한 노드의 이웃들을 설명합니다. 주어진 노드는 항상 val = 1인 첫 번째 노드입니다. 복제된 그래프의 주어진 노드의 복사본을 참조로 반환해야 합니다.

제약

· The number of nodes in the graph is in the range [0, 100].
· 1 ≤ Node.val ≤ 100
· Node.val is unique for each node.
· There are no repeated edges and no self-loops in the graph.

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[[2,4],[1,3],[2,4],[1,3]]

[[2,4],[1,3],[2,4],[1,3]]

example 2input → output

[[]]

[[]]

example 3input → output

[]

[]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
깊은 복제(deep copy)란 정확히 무엇을 의미하나요?
☐
그래프에 사이클이 있으면 어떻게 무한 루프를 방지할 수 있나요?
☐
새 노드를 생성한 후, 이웃을 처리하기 전에 메모에 등록해야 하나요, 아니면 후에 등록해야 하나요?
☐
이 문제를 푸는 데 BFS가 DFS보다 낫나요?
☐
메모 맵 대신 방문한 노드를 추적하는 집합(set)만 사용할 수 있나요?
☐
입력 노드가 null인 경우는 어떻게 처리하나요?
☐
원본 그래프를 수정하지 않으면서 복제할 수 있나요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 메모이제이션 맵 초기화

○

oldToNew = {}

○

visited = set()

○

oldToNew = []

step 2· 메모에서 확인 (이미 복제됨)│ 중첩

○

if node in oldToNew:

○

if node in visited: continue

○

if node.val in oldToNew: return oldToNew[node.val]

step 3· 새 노드 생성│ 중첩

○

copy = Node(node.val)

○

copy = Node()

○

copy = node

step 4· 메모에 등록 (사이클 처리)│ 중첩

○

oldToNew[node] = copy

○

oldToNew[copy] = node

○

# Register after processing neighbors loop

step 5· 이웃 노드 재귀 복제│ 중첩

○

for nei in node.neighbors:

○

copy.neighbors = [dfs(nei) for nei in node.neighbors]

○

copy.neighbors.extend(node.neighbors)

step 6· 복제된 노드 반환│ 중첩

○

return copy

○

return node

○

return copy.neighbors

step 7· null 입력 처리

○

return dfs(node) if node else None

○

return dfs(node)

○

if node: dfs(node) 
return None

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def cloneGraph(self, node: "Node") -> "Node":

        oldToNew = {}

        def dfs(node):

            if node in oldToNew:

                return oldToNew[node]

            copy = Node(node.val)

            oldToNew[node] = copy

            for nei in node.neighbors:

                copy.neighbors.append(dfs(nei))

            return copy

        return dfs(node) if node else None

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[[2,4],[1,3],[2,4],[1,3]]

→

[[2,4],[1,3],[2,4],[1,3]]

case 2

[[]]

→

[[]]

case 3

[]

→

[]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.