https://leetcode.com/problems/clone-graph/?envType=study-plan-v2&envId=top-interview-150

133. Clone Graph

⭐ 문제

연결된 무방향 그래프의 노드에 대한 참조가 주어졌을 때, 그래프의 깊은 복사본(클론)을 반환해야 합니다
그래프의 각 노드는 값 (정수)과 이웃 노드들의 목록 (List[Node])을 포함하고 있습니다.

class Node {
    public int val;
    public List<Node> neighbors;
}

테스트 케이스 형식은 다음과 같습니다:
간단히 말해, 각 노드의 값은 노드의 인덱스와 같습니다 (1로 시작하는 인덱스). 예를 들어, 값이 1인 첫 번째 노드, 값이 2인 두 번째 노드, 이런 식으로 진행됩니다. 그래프는 인접 리스트를 사용하여 표현됩니다.
인접 리스트는 유한 그래프를 나타내는 데 사용되는 정렬되지 않은 목록의 모음입니다. 각 목록은 그래프의 노드의 이웃을 설명합니다.
주어진 노드는 항상 값이 1인 첫 번째 노드일 것입니다. 당신은 주어진 노드의 복사본을 반환해야 하며, 이는 클론된 그래프의 참조로 반환되어야 합니다.

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

🤔 접근 방향

깊은 복사를 수행하기 위해 깊이 우선 탐색 (Depth-First Search, DFS) 알고리즘을 활용할 것입니다. 주어진 시작 node를 기반으로 graph를 복사하며, 이미 복사한 node들은 중복 복사를 피하기 위해 HashMap을 활용합니다. HashMap은 원본 node를 key로 하고 해당 node의 복제본을 value로 매핑하여 빠르게 참조할 수 있도록 합니다. 이렇게 구현된 알고리즘은 주어진 graph의 모든 node와 이웃 node를 깊은 복사하여 문제에서 요구한 클론를 생성하는 역할을 합니다.

✍️ 의사 코드

함수 cloneGraph(node):
    만약 node가 null이면:
        null을 반환

    만약 cloneMap에 node가 이미 포함되어 있다면:
        cloneMap에서 해당 node의 복제본을 반환

    새로운 clonedNode 생성:
        clonedNode의 값(val)를 node의 값으로 설정
        clonedNode의 이웃 리스트(neighbors)를 빈 리스트로 초기화
        cloneMap에 node를 key로 하고 clonedNode를 value로 추가

    node의 각 이웃 neighbor에 대해서 반복:
        clonedNode의 이웃 리스트에 cloneGraph(neighbor)를 추가

    clonedNode 반환

✅ 나의 풀이

class Solution {
    private Map<Node, Node> cloneMap = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }

        // 이미 복사한 노드인 경우, 복사본을 반환
        if (cloneMap.containsKey(node)) {
            return cloneMap.get(node);
        }

        // 새로운 노드 생성
        Node clonedNode = new Node(node.val, new ArrayList<>());
        cloneMap.put(node, clonedNode);

        // 이웃 노드들을 복사하고 연결
        for (Node neighbor : node.neighbors) {
            clonedNode.neighbors.add(cloneGraph(neighbor));
        }

        return clonedNode;
    }
}

🖥️ 결과

Runtime: 25 ms
Memory Usage: 41.7 MB