리트코드 133 그래프 클론 c++ // 그래프 복사하는방법

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

 

1. 의사코드

1. map에 <원본노드포인터, 복제노드포인터> 를 담는다.

2. 엣지케이스 : 원래널인경우 return null

root에 이웃이없는경우, 그거 new로 생성해서 리턴

3. dfs

초기화 : cur(원본)배열의 값으로 노드를 만들어주고, 이웃만 채워주면 된다!!

이웃에대해, 이미 클론되었다면(맵에 존재한다면 == 유사 visited) 이웃에 담아준다.

아니라면, 거기로 들어간다.

4. 아래그림에서 1에서 시작하는 dfs를 돌려보면 이해가 될것이다.

class Solution {
public:
    Node* dfs(Node* cur, unordered_map<Node*, Node*>& mp) {
        vector<Node*> neighbour;
        Node* clone = new Node(cur->val);  // Create a clone of the current node
        mp[cur] = clone;  // Store the clone in the map // 유사방문처리!

        for (auto it : cur->neighbors) {  // Iterate through neighbors
            if (mp.find(it) != mp.end()) {  // If neighbor is already cloned
                neighbour.push_back(mp[it]);  // Add cloned neighbor from map
            } else {
                neighbour.push_back(dfs(it, mp));  // Recursively clone the neighbor
            }
        }
        
        clone->neighbors = neighbour;  // Assign cloned neighbors to the clone
        return clone;
    }

    Node* cloneGraph(Node* node) {
        unordered_map<Node*, Node*> mp;  // Map to store original node to clone mapping
        if (node == NULL) {
            return NULL;  // If input node is NULL, return NULL
        }
        if (node->neighbors.size() == 0) {  // If the graph has only one node
            Node* clone = new Node(node->val);  // Clone the single node
            return clone;
        }
        return dfs(node, mp);  // Start DFS to clone the graph
    }
};