23.03.23. 풀었던 문제들

Leetcode 1319. Number of Operations to Make Network Connected

 처음에는 [사용하지 않는 edge 개수]를 구하면 된다고 생각했다. 그래서 각 edge에 사용 여부를 표시하고 전체 DFS 후 disjoint set의 개수를 알아내고, 사용하지 않은 edge 개수를 알아내면 문제를 풀 수 있을 거라 생각했다.

 

 그러나 각 edge에 사용 여부를 표시하는 것이 까다로웠다. 굳이 이렇게 풀어야 하나? 라는 생각도 들고. 그러다가 어제 푼 union-find 문제가 생각났다. 어? union-find로 풀면 쉽게 풀리겠는데? 로직은 아래와 같다.

• 모든 edge에 대해 union한다.
  • 이 때 다른 disjoint set인 경우(root가 다른 경우)에는 두 disjoint set을 합쳐주어야 한다.
  • 이미 같은 disjoint set에 있는 경우에는 해당 케이블을 사용할 필요가 없다.
• 이 방법으로 필요없는 케이블 수를 얻고, 전체를 순회하며 root 개수를 구한다.

 

첫 번째 접근

 실수한 점은, numGroup를 바로 리턴한 것. n개의 disjoint group을 연결하기 위해서는 n-1개가 필요하다. 따라서 numGroup - 1을 리턴해야 했다.

// Runtime 139 ms Beats 61.43%
// Memory 44.1 MB Beats 53.23%

class Solution {
public:
    vector<int> parent;
    int find(int v){
        if(parent[v] == v) return v;

        parent[v] = find(parent[v]);
        return parent[v];
    }
    int makeConnected(int n, vector<vector<int>>& connections) {
        parent.resize(n);
        for(int i = 0; i<n; i++) parent[i] = i;

        int needless = 0;
        for(vector<int> connection : connections){
            int rx = find(connection[0]), ry = find(connection[1]);
            if(rx != ry){
                parent[rx] = ry;
            }
            else{
                needless++; // 이미 같은 그룹
            }
        }

        set<int> s;
        for(int i = 0; i<n; i++){
            s.insert(find(i));
        }
        int numGroups = s.size();
        numGroups--; // *** 실수 : n개의 group을 연결하기 위해서는 n-1개의 케이블이 필요

        if(numGroups > needless) numGroups = -1;
        return numGroups;
    }
};

시간복잡도

 union-find에 O(mlog*n). m은 edge 개수이다. 그리고 set에 넣을 때 worst n개가 들어가므로 O(nlogn)이다.

 

공간복잡도

 set과 parent 배열을 사용하므로 O(n)이다.

 

 

최적화

 위 코드에서 조금 최적화할 수 있다. set으로 root를 세는 게 아니라, find(i) == i인 것들이 numGroups의 개수라고 생각하는 것이다. 이것들은 root를 유지하고 있는 것이기 때문이다. 

// Runtime 130 ms Beats 74.83%
// Memory 41.8 MB Beats 80.41%

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        // ...

        int numGroups = -1;
        for(int i = 0; i<n; i++){
            if(find(i) == i) numGroups++;
        }

        if(numGroups > needless) numGroups = -1;
        return numGroups;
    }
};

시간복잡도

 union-find에 O(mlog*n). m은 edge 개수이다. 그리고 set에 넣지 않기 때문에 이 부분은 O(n). 따라서 O(mlog*n)이다.

 

공간복잡도

 parent 배열만 사용하므로 O(n)이다.

 

 

두 번째 접근

 다른 방법도 있다. 바로 tree의 성질을 활용하는 것. n개의 vertex를 연결하기 위해서 n-1개의 edge가 필요하다. 즉슨, n-1개를 초과하는 edge는 disjoint set을 연결하는 데 사용할 수 있다는 말이다.

 따라서 DFS로 disconnected group의 개수를 세고, n-1개를 초과하는 edge를 연결하는 데만 사용할 수 있다.

// Runtime 145 ms Beats 52.54%
// Memory 51 MB Beats 41.15%

class Solution {
public:
    vector<bool> visited;
    vector<vector<int>> edges; // edges[i] : i에서 출발하는 vertex의 도착 vertex vector
    void DFS(int v){        
        for(int w : edges[v]){
            if(!visited[w]){
                visited[w] = true;
                DFS(w);
            }
        }
    }
    int makeConnected(int n, vector<vector<int>>& connections) {
        int numConnections = connections.size();
        if(numConnections < n-1) return -1;

        edges.resize(n);
        for(vector<int> &connection : connections){
            edges[connection[0]].push_back(connection[1]);
            edges[connection[1]].push_back(connection[0]);
        }
        visited.resize(n);
        fill(visited.begin(), visited.end(), false);

        int numGroups = 0;
        for(int i = 0; i<n; i++){
            if(!visited[i]){
                numGroups++;
                visited[i] = true;
                DFS(i);
            }
        }

        return numGroups - 1;
    }
};

시간복잡도

 DFS에 O(V + E)를 사용한다. 끝!

 

공간복잡도

 edges vector에 O(E), vertex vector에 O(V)가 들어간다. 따라서 O(V + E).

 

 

후기

 Union-find를 쓸 때, 꼭 rank를 사용할 필요가 없다는 걸 문제 풀면서 계속 느낀다. find 함수에 path compression만 잘 넣어주어도 상당히 빠른 속도로 돈다! 기억하자.