[LeetCode] 133. Clone Graph, Medium

1. 문제

• val와 neighbors 필드를 가지는 노드로 구성된 그래프가 주어질 때, 이를 원래 노드를 참조하지 않는 새로운 노드로 구성된 그래프를 구성하라.

2. 해결

/**
 * Definition for _Node.
 * class _Node {
 *     val: number
 *     neighbors: _Node[]
 * 
 *     constructor(val?: number, neighbors?: _Node[]) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.neighbors = (neighbors===undefined ? [] : neighbors)
 *     }
 * }
 * 
 */

function DFS(node: _Node, visited: Map<Node, Node>): _Node | null {
    if(visited.has(node)){
        return visited.get(node);
    }
    
    visited[node.val] = true;
    
    const clone = new _Node(node.val);
    visited.set(node, clone);
    for(const neighbor of node.neighbors) {
        clone.neighbors.push(DFS(neighbor, visited))
    }
    return clone;
}

function cloneGraph(node: _Node | null): _Node | null {
	if(!node) return null;
    
    const visited = new Map<Node, Node>();
    
    return DFS(node, visited);
};

• 처음에는 visit 판별을 배열을 선언해두고 boolean을 통해 판별하려고 했는데, 도저히 해결이 되지 않아서 다른 사람 풀이를 참고했다.
• visit을 Map으로 구성하여, 복제한 노드를 이곳에 저장해두고 꺼내서 쓴다.
• 방문했던 노드면 Map에서 반환하고, 그렇지 않으면 복제한 뒤 저장한다.
• 복제한 노드의 neighbors 필드를 채우기 위해 기존 neighbors 노드를 DFS 탐색한 뒤 복제한 노드를 반환하면, 해당 노드로 복제한 노드의 neighbors 필드가 채워진다.