[Leetcode] 133. Clone Graph - JS

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

 

1. 문제 분석

문제분석
--------------------
연결된 무방향 그래프의 노드에 대한 참조가 주어질 때,
그래프의 전체 복사본을 반환하라.

제한조건
--------------------
- 노드의 총 갯수는 0 ~ 100개이다.
- 1 <= Node.val <= 100
- 반복되는 간선이나 자가 루프는 없다.
- 그래프는 연결되어 있고 해당 노드로부터 모든 노드를 방문할 수 있다.

 

2. 접근 방법 - DFS

접근방법
--------------------
DFS(깊이우선탐색)으로 접근한다.

visited 변수를 Map 자료구조로 초기화하고
원본노드의 참조값 => 복사된 노드의 참조값으로 매핑하여 이미 방문한 노드 처리를 해준다.

재귀함수 내부에서 방문한 원본 노드라면.. 복사된 노드를 반환해주고
그렇지 않다면 노드를 복사하여 visited에 추가한 뒤
복사한 노드의 neigbors에 원본 노드의 neighbors를 재귀적으로 복사한 값을 추가해줘야한다.

결과적으로 모든 이웃에 대해 재귀적으로 복사한 값을 추가해주고나면 복사한 값을 반환한다.

 

 

3. 코드

/**
 * // Definition for a _Node.
 * function _Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {_Node} node
 * @return {_Node}
 */
var cloneGraph = function(node) {
    if (!node) return;

    const visited = new Map();
    
    function dfs(node) {
        if (visited.has(node)) {
            return visited.get(node);
        }

        const newNode = new _Node(node.val);
        
        visited.set(node, newNode);

        for (const neighbor of node.neighbors) {
            newNode.neighbors.push(dfs(neighbor));
        }
        
        return newNode;
    }

    return dfs(node);
};

 

 

4. 복잡도 분석

- 시간복잡도: O(V * E), V는 노드의 수, E는 간선의 수

- 공간복잡도: O(V)

 

DFS 탐색으로 접근하는 것 까진 알아냈지만, 재귀적으로 함수를 구현할 때, 어떤 파라미터를 넣고 어떤 값을 반환하고 어떤 위치에서 호출해야할지에 대한 방법이 아직까지도 익숙하지 않은 것 같다.

이웃들이 Node의 배열이라고 하니 이웃들을 하나씩 복사해서 간선을 추가해주는 것은 알아냈지만,

어떻게 재귀적으로 이웃들을 복사해서 간선에 추가할지 구현하는 것이 어려운 것 같다..

 

claude에게 물어봐서 공부했다. 여러번 반복해서 이해하면서 푸는 방법으로 익숙하게 해야겠다.