[자료구조와 알고리즘] 133. Clone Graph

문제 풀이

Leetcode - Top Interview 150 - 133. Clone Graph

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

위의 노드 구조로 이루어진 그래프를 깊은 복사해서 반환하는 문제입니다.

제한 사항으로는
1. 그래프의 노드 수는 0 ~ 100개
2. 1 <= Node.val <= 100
3. Node.val은 각 노드마다 고유한 값이다.
4. 반복되는 간선(repeated edges)이나 자가 순환(self-loops)이 없다. (단순 경로 그래프)
5. 그래프가 연결되어 있으며 주어진 노드에서 시작하여 모든 노드를 방문할 수 있다.

풀어보기

아래 풀이는 DFS 깊이탐색으로 풀이한 코드입니다.

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

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
	// 방문 노드 기록
  	// 바로 탐색하는 함수 dfs를 시작하지 않고 이 변수가 밖에 있어야 합니다.
    const visited = {};

    const dfs = (node) => {
        if (!node) return node;
      	// visited에 node.val이 있다면 탐색
        if (visited[node.val]!=null) return visited[node.val];

      	// 새로운 루트 노드를 만들고 visited에 넣어줍니다.
        const root = new Node(node.val);
        visited[node.val] = root;

      	// 이웃 노드를 탐색하면서 루트 노드에 dfs로 탐색한 결과를 넣어줍니다.
        node.neighbors.forEach(n => root.neighbors.push(dfs(n)))
        return root;
    }

    return dfs(node);

시간 복잡도와 공간 복잡도는 모두 O(N)입니다.

마무리

풀이만 보면 너무 쉬워보이지만, 사실 너무 오랫동안 못 풀어서 검색해서 풀었습니다..🥲
다음 포스트는 그래프 개념을 제대로 공부하고 구현하는 주제로 해야겠습니다.