[ leetcode ] 133. Clone Graph

해당 문제는 Node로 구성된 Graph를 그대로 복제한 그래프를 반환하는 문제입니다. 기존에 주어진 Node를 그대로 반환하면 안되고 새로 생성하여 반환해야 합니다.

BFS를 사용하여 Root Node에서 출발하여 해당 노드를 복제하고, 인접한 노드들을 Queue에 추가하고 다시 반복하는 방식으로 구현하였습니다. 이 과정에서 Hash Table을 사용하여 기존 Node가 key가 되고 새로 복제된 Node를 value로 추가하여 방문한 인접노드를 중복으로 생성하거나 BFS Queue에 추가하는 것을 방지하였습니다.

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
#include <map>
#include <queue>

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return node;

        map<Node*, Node*> hash_table;
        hash_table[node] = new Node(node->val);

        queue<Node*> queue;
        queue.push(node);

        while (!queue.empty()) {
            Node* temp = queue.front();
            queue.pop();

            for (auto adjacent : temp->neighbors) {
                if (hash_table.find(adjacent) == hash_table.end()) {
                    hash_table[adjacent] = new Node(adjacent->val);
                    queue.push(adjacent);
                }
                hash_table[temp]->neighbors.push_back(hash_table[adjacent]);
            }
        }
        return hash_table[node];
    }
};