solution

/**
 * // 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 null;
    }

    const map = new Map();
    
    function traverse(root){
        if(!map.has(root.val)){
            map.set(root.val, new Node(root.val));
            
            map.get(root.val).neighbors = root.neighbors.map(traverse);
        }

        return map.get(root.val);
    }

    return traverse(node);
};

neighbors의 neighbors의 neighbors...
이런 식으로 진행되는, 꼬리의 꼬리를 물고 계속해서 들어가는(혹은 반복하는) 문제이기 때문에
Recursion, 그리고 DFS가 떠올랐다.

Hash Map을 이용하여 한번 순회한 node를 관리하면서 진행하는 방식을 사용했다.
만약, Hash Map에 없는 node가 들어왔다면 node.val을 key로 하고, new Node()를 value로 하는 pair를 생성한다.

이 후, 현재 root, 즉, 생성된 node의 neighbors를 설정해준다.
현재 map() 연산이 진행되는 것은 traverse()의 인자로 받아온 node의 neighbors이며,
이는 map.get(root.val).neighbors와는 전혀 다른 것이다.
Hash Map 쪽은 아무 데이터도 없는 상태이며,
root는 문제에 주어진 함수가 시작될 때 받아온 node로부터 흘러나오는 정보이기 때문이다.

이 부분은 코드만 보면 이해가 어려울 수 있는데, 아래 출력을 보자.
map() 연산 직후에 map.get(root.val)을 콘솔로 출력한 것이다.

node {
  val: 4,
  neighbors: [ { val: 1, neighbors: [] }, { val: 3, neighbors: [] } ]
}
node {
  val: 3,
  neighbors: [ { val: 2, neighbors: [] }, { val: 4, neighbors: [Array] } ]
}
node {
  val: 2,
  neighbors: [ { val: 1, neighbors: [] }, { val: 3, neighbors: [Array] } ]
}
node {
  val: 1,
  neighbors: [ { val: 2, neighbors: [Array] }, { val: 4, neighbors: [Array] } ]
}

1번 node의 neighbors 중 2번 node가 먼저 Recursion되고,
2번 node의 neighbors 중 1번은 이미 Hash Map에 저장되었으므로 3번 node가 Recursion,
3번 node의 neighbors 중 2번은 이미 Hash Map에 저장되었으므로 4번 node가 Recursion,
4번 node의 neighbors는 이미 모두 Hash Map에 있기 때문에, key에 들어있는 value, 즉, node를 반환하고
Recursion됐던 것들이 순차적으로 return이 되어가며 위와 같은 출력이 완성된다.

Hash Map에 없는 key를 따라 깊게 들어갔다가,
다시 반대로 빠져나오면서 각각의 neighbors를 구성해 나가는 것이다.

Hash Map을 사용하는 것은 이러한 연산들을 하기 위한 이유도 있지만,
복사된 값을 만들어내기 위함도 있다.

다른 분의 solution

var cloneGraph = function(node) {
    // If start node is null then we can't do any cloning
    let start = node; 
    if (start === null) return null;
    // vertexMap is the original node reference to our node
    const vertexMap = new Map(); 
    
    
    // Add the start node to the queue. Give the start node a clone in the vertex map
    const queue = [start]
    vertexMap.set(start, new Node(start.val)); 
    
    /*
    * Breadth first search continues until we process all the vertices in the graph
    * In the original graph. We know this is done when queue is empty
    */
    
    while (queue.length > 0) {
        // We grab a node. We will express all of the edges coming off of this node.
        const currentVertex = queue.shift(); 
        // Iterate over all adjacents.
        for (const neighbor of currentVertex.neighbors) {
          // Has this neighbor been given a clone?
            if (!vertexMap.has(neighbor)) {
                /*
                * No? Give it a mapping and add the original neighbor to the search queue so we
                * can express ITS edges later
                */
                vertexMap.set(neighbor, new Node(neighbor.val))
                queue.push(neighbor); 
            }
            
            /*
            * Draw the edge from currVertex's clone to neighbor's clone. Do you see how our
            * hashtable makes this quick access possible?
            */
            vertexMap.get(currentVertex).neighbors.push(vertexMap.get(neighbor)); 
        }
    }
   return vertexMap.get(start); 
    
};

필자는 DFS 느낌으로 접근을 했는데, BFS를 사용하신 분도 계신다.
Tree에서 자주 구현해왔던 BFS에 필자가 사용한 Hash Map 방식을 채택하신 것으로 보인다.
반복을 사용하셨지만 결과적으로는 재귀와 다를 것은 없다.
Hash Map이 key를 가지고 있는지 없는지에 따라 queue를 계속 넣어주느냐 마느냐가 달라지기 때문이다.