[Graph General][Medium] 133. Clone Graph

https://leetcode.com/problems/clone-graph/description 

Q. 주어진 그래프를 deep copy 하여 반환하라. 

 

 

Solution

 기존 graph를 순회하며 모든 node의 포인터를 중복되지 않게 우선 저장한다. 

 이후 각 노드의 neighbors만큼 새로운 node를 만든다. 

 새로운 노드를 순회하며, 각자의 neighbors에 새로운 node를 link한다. 

 

 코드 

 

Node* cloneGraph(Node* node) 
{
    if(node == nullptr) return node;

    // adding nodes into map.
    set<Node*> setNodes;
    queue<Node*> qBuff;
    qBuff.push(node);
    while(qBuff.size() > 0)
    {
        Node* node2 = qBuff.front();
        qBuff.pop();
        if(setNodes.find(node2) != setNodes.end())
            continue;

        setNodes.insert(node2);
        for(int q = 0; q < node2->neighbors.size(); ++q)
            qBuff.push(node2->neighbors[q]);
    }

    //cout << "set size : " << setNodes.size() << endl;

    map<int, Node*> mapNodes;
    for(auto iter = setNodes.begin(); iter != setNodes.end(); ++iter)
    {
        Node* cur = *iter;
        if(mapNodes.find(cur->val) == mapNodes.end())
        {
            Node* newNode = new Node(cur->val);
            mapNodes[cur->val] = newNode;
        }
    }

    //cout << "map size : " << mapNodes.size() << endl;

    for(auto iter = setNodes.begin(); iter != setNodes.end(); ++iter)
    {
        Node* cur = *iter;
        Node* target = mapNodes[cur->val];
        for(int q = 0; q < cur->neighbors.size(); ++q)
        {
            target->neighbors.push_back( mapNodes[cur->neighbors[q]->val ] );
        }
    }
    return mapNodes[node->val];
}

 

결과