23.04.08. 풀었던 문제들

Leetcode 133. Clone Graph

 Node pointer로 이루어진 graph 하나를 clone하는 문제. 중복된 edge는 없고, 각 Node가 가지고 있는 val은 unique하다는 조건에서 시작한다.

 사실상 그렇게 어려운 문제는 아니다. DFS나 BFS를 쓰고, 그 과정에서 몇 줄만 추가해 주면 되는 문제.

 

첫 접근

 일단 BFS로 풀었다. naive하게 2번의 BFS를 했다.

• 첫 BFS에서는 unvisit인 모든 Node에 대해 clone을 생성한다. 생성한 Node clone들을 value를 key로 가지는 map에 저장한다. ... 1
• 두 번째 BFS에서는 edge를 연결한다. 첫 번째 BFS에서 모든 Node를 찾았기 때문에 두 번째 BFS에서는 모든 clone들의 edge만 연결해 주면 된다.

// Runtime 9 ms Beats 23.26%
// Memory 8.8 MB Beats 65.38%

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

        queue<Node*> q;
        set<Node*> visited;
        map<int, Node*> m; // mapper of clone node 

        // ...1
        q.push(node);
        visited.insert(node);
        while(!q.empty()){
            Node* origin = q.front(); q.pop();
            visited.insert(origin);

            if(m.find(origin->val) == m.end()){
                m[origin->val] = new Node(origin->val);
            }

            for(Node* adj : origin->neighbors){
                if(visited.find(adj) == visited.end()){
                    q.push(adj);
                }
            }                        
        }
 
        // ... 2
        q.push(node);
        visited.clear();
        visited.insert(node);
        while(!q.empty()){
            Node* origin = q.front(); q.pop();
            visited.insert(origin);

            for(Node* adj : origin->neighbors){
                if(visited.find(adj) == visited.end()){
                    m[origin->val]->neighbors.push_back(m[adj->val]);
                    m[adj->val]->neighbors.push_back(m[origin->val]);
                    q.push(adj);
                }
            }                        
        }

        return m[1];
    }
};

 

 

두 번째 접근

 BFS 1번으로 해결할 수 없을까? 가능할 거라 생각했다. BFS에서 unvisit한 Node를 방문할 때 새 Node를 생성하고 map에 넣는다. 그렇지 않다면 이미 map에 들어가 있는 상태일 것이다.

 따라서 어떤 Node의 neighbor를 탐색할 때 edge를 바로 연결해 줄 수 있다.

// Runtime 7 ms Beats 61.34%
// Memory 8.8 MB Beats 53.37%

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

        queue<Node*> q;
        set<Node*> visited;
        map<int, Node*> m; // mapper of clone node 

        q.push(node);
        visited.insert(node);
        while(!q.empty()){
            Node* origin = q.front(); q.pop();
            visited.insert(origin);

            if(m.find(origin->val) == m.end()){
                m[origin->val] = new Node(origin->val);
            }

            for(Node* adj : origin->neighbors){
                if(m.find(adj->val) == m.end()){
                    m[adj->val] = new Node(adj->val);
                    q.push(adj);
                }
                m[origin->val]->neighbors.push_back(m[adj->val]);
            }                        
        }

        return m[1];
    }
};

 

 

세 번째 접근

 조금 더 최적화했다. BFS의 모든 단계에서 [현 Node가 unvisit이면 새로운 Node를 생성]하고, 또 [현 Node의 모든 neighbor를 탐색할 때 unvisit이면 새로운 Node를 생성]하는 로직이 겹치기 때문에 이를 수정했다. 또 사용하지 않는 visited set을 버렸다.

// Runtime 7 ms Beats 61.34%
// Memory 8.7 MB Beats 65.38%

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

        queue<Node*> q;
        map<int, Node*> m; // mapper of clone node 

        if(m.find(node->val) == m.end()){
            m[node->val] = new Node(node->val);
        }

        q.push(node);
        while(!q.empty()){
            Node* origin = q.front(); q.pop();

            for(Node* adj : origin->neighbors){
                if(m.find(adj->val) == m.end()){
                    m[adj->val] = new Node(adj->val);
                    q.push(adj);
                }
                m[origin->val]->neighbors.push_back(m[adj->val]);
            }                        
        }

        return m[1];
    }
};

 

 

시간복잡도

 각 접근마다 BFS를 2번, 또는 1번 하므로 O(V+E).

 

공간복잡도

 worst case q, visited, set에 각각 O(V)만큼 들어간다. 따라서 O(V)