Clone Graph

방향이 지정되지 않는 그래프의 노드 하나를 받는다.

노드에는 노드값과 연결되어 있는 노드들의 벡터 데이터들이 있는데,

이 데이터들을 이용해 그래프를 복사하여 복사된 그래프의 노드 하나를 반환하는 것이 문제이다.

또한 노드값은 1부터 시작하며 유니크하다는 조건이 있다.

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

class Solution {
public:
    Node* cloneGraph(Node* node) {
        
        if (node == NULL)
        {
            return NULL;
        }

        unordered_map<int, Node*> nodes;
        queue<Node*> waitings{};

        Node* root = new Node(node->val);
        nodes[node->val] = root;

        waitings.push(node);
        while (waitings.empty() == false)
        {
            Node* nowNode = waitings.front();
            waitings.pop();
            for (auto& neighbor : nowNode->neighbors)
            {
                if (nodes.count(neighbor->val) == 0)
                {
                    nodes[neighbor->val] = new Node(neighbor->val);
                    waitings.push(neighbor);
                }

                nodes[nowNode->val]->neighbors.emplace_back(nodes[neighbor->val]);
            }
        }

        return root;
    }
};