[LeetCode] Clone Graph - Javascript

Clone Graph

[주어지는 그래프 복제하기]

제약 조건 

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.
The Graph is connected and all nodes can be visited starting from the given node.

Example

문제 접근 방식

node의 neighbors를 돌고 또 거기에 존재하는 neighbors가 존재하기에, 재귀 방식의 dfs로 문제 풀이가 가능했다.

visited 객체를 생성해 순회하고 있는 노드가 방문한 노드인지 확인한다.

node.val 값을 key로 지정해 주어지는 노드를 복제할 생각으로 코드를 작성했다.

 

처음 주어지는 노드를 복제하고, 해당 노드의 neighbors들을 재귀 호출해 복제를 한다.
만약 이미 visited 객체에 존재할 경우 리턴을 해 중복 순회가 일어나지 않도록 하고,
아니라면 해당 노드를 복제하고 visited에 등록한다.

 

node가 없을 경우 예외 처리를 위해 node가 null이라면 그대로 node를 리턴하도록 한다.

sovle 코드

/**
 * // 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) {
    
    var visited = {};
    
    let dfs = function(node) {
        if (!node){
            return node;
        }

        if (visited[node.val]!=null){
            return visited[node.val];
        } 
        
        let root = new Node(node.val);

        visited[node.val] = root;

        for (let n of node.neighbors) {
            root.neighbors.push(dfs(n));
        }

        return root;
    }
    
    return dfs(node);
};