[LeetCode] 133. Clone Graph 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Clone Graph (핵심은 “값 복사”가 아니라 “연결 구조 복사”였다)

---

 

문제 요약 (Clone Graph)

연결된 무방향 그래프의 시작 노드가 주어질 때,
그래프 전체를 깊은 복사(Deep Copy) 해서 새로운 그래프의 시작 노드를 반환하는 문제

 

문제링크: https://leetcode.com/problems/clone-graph

 

---

그래프는 트리처럼 깔끔하지 않다.

• 사이클(cycle) 이 있을 수 있고
• 같은 노드가 여러 경로로 다시 등장한다

즉, 아무 생각 없이 DFS로 복사하면

• 사이클 때문에 무한 재귀
• 같은 노드를 여러 번 복사해서 구조가 깨짐

😮 여기서 관점을 바꿔야 한다.
이 문제는 “노드 값을 복사하는 문제”가 아니라
👉 “노드 사이의 연결 관계(참조 구조) 를 그대로 복사하는 문제”다.

 

그래서 질문을 이렇게 바꾼다.
👉 “이 원본 노드를 복사한 새 노드는 어디에 저장해두고 재사용하지?”

정답은 Map(visited) 이다.
“원본 노드 → 복사 노드” 매핑을 저장하면 된다.

---

🔹 깊은 복사(Deep Copy)란 무엇인가?

복사에는 두 가지가 있다.

1️⃣ 얕은 복사 (Shallow Copy)

객체의 참조(주소)만 복사한다.

 

Node a = original;

 

이 경우,

• a와 original은 같은 객체를 가리킨다
• 하나를 수정하면 다른 하나도 같이 바뀐다

👉 사실상 복사가 아니다.

 

2️⃣ 깊은 복사 (Deep Copy)

객체 자체를 새로 만들고,
그 내부에 연결된 객체들까지 전부 새로 만든다.

예를 들어:

 

1 -- 2

 

깊은 복사 후:

 

1' -- 2'

• 값은 동일
• 구조도 동일
• 하지만 메모리 주소는 완전히 다름

Clone Graph 문제는 바로 이 깊은 복사를 요구한다.

---

💡 핵심 아이디어

 

그래프에는 사이클이 있다.
그래서 반드시 “이미 복사한 노드”를 기억해야 한다.

• 그래프는 사이클/재방문이 가능 → 방문 체크 필수
• Map<원본노드, 복사노드> 를 만들어 두고
  • 이미 복사한 노드는 그대로 반환
  • 처음 보는 노드는 새로 만들고 Map에 저장
• 이후 neighbor들을 재귀적으로 복사하며 연결

---

 

코드 (Java)

• 핵심: Map의 key는 val이 아니라 “원본 노드 객체” 로 잡는 게 안전하다. (val이 항상 유일하다는 보장이 없을 수 있기 때문)

class Solution {
  public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> visited = new HashMap<>();
    return dfs(node, visited);
  }

  private Node dfs(Node node, Map<Node, Node> visited) {
    if (visited.containsKey(node)) return visited.get(node);

    Node newNode = new Node(node.val);
    visited.put(node, newNode);

    for (Node neighbor : node.neighbors) {
      newNode.neighbors.add(dfs(neighbor, visited));
    }

    return newNode;
  }
}

 

 

📈 Time / Space Complexity

• 시간: O(N + E) (노드 N개, 간선 E개를 한 번씩 돈다)
• 공간: O(N) (visited 맵 + 재귀 스택)

---

 

📝 이번 문제에서 얻은 깨달음

• 깊은 복사는 값이 아니라 참조 구조를 복사하는 것
• 사이클이 있을 때, 방문 체크가 없으면 무한 루프다!
• Clone 문제는 거의 항상 “원본 → 복사본 매핑”이 필요하다
• Map<Integer, Node>(val 기준)은 운 좋으면 되지만(이번 문제는 val이 모두 unique한 값이라 통과함), 정석은 Map<Node, Node> (원본 객체 기준)

 

Clone Graph는
“그래프가 다시 만나는 구조를 이해하고, 복사본을 재사용하는 문제”였다.