23.04.29. 풀었던 문제들

1697. Checking Existence of Edge Length Limited Paths

 edge 간 weight가 있는 어떤 graph와 [vertex 1, vertex 2, limit]으로 주어지는 query list가 있을 때 각 query의 vertex 1부터 vertex 2까지 path 중 max값이 limit보다 작으면 true를, 아니면 false를 계산하는 문제. vertex 개수를 V, edge 개수를 E, query 개수를 Q라고 했을 때 0 <= V, E, Q <= 100,000이기 때문에 nlogn 이하로 풀어야 한다.

• limit을 기준으로 queries, edgeList 오름차순 정렬
• union-find를 이용하면 어떤 두 vertex가 이어져있는지 아닌지 쉽게 알 수 있다.(root를 찾고, 같다면 이어져 있는 것) 이 특징을 이용한다.
• 모든 query에 대해 아래 사항을 반복한다.
  • 어떤 query의 limit보다 작은 모든 edge weight를 union한다.
  • 그 결과로 해당 query limit보다 작은 모든 edge들이 union되며, 이 때 query가 가지고 있는 vertex 1과 vertex 2의 root가 같으면 query limit보다 작은 edge들로 두 vertex가 이어진다. 아닌 경우 이어지지 않는다.

// Runtime 652 ms Beats 48.55%
// Memory 110.1 MB Beats 78.84%

bool cmp(vector<int>& a, vector<int>& b){
    if(a[2] < b[2]) return true;
    else return false;
}

class Solution {
public:
    vector<int> parent, rank;
    void makeDS(int n){
        parent.resize(n);
        for(int i = 0; i<n; i++) parent[i] = i;
        rank.resize(n, 0);
    }

    int find(int x){
        if(x == parent[x]) return x;
        parent[x] = find(parent[x]);
        return parent[x];
    }

    void join(int x, int y){
        int rx = find(x), ry = find(y);

        if(rank[rx] > rank[ry]){ // ry가 rx 아래로 들어감
            parent[ry] = rx;
        }
        else{
            if(rank[rx] == rank[ry]){
                rank[ry]++;
            }
            parent[rx] = ry;
        }
    }

    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        for(int i = 0; i<queries.size(); i++){
            queries[i].push_back(i); // index 추가
        }

        // limit 오름차순 정렬
        sort(queries.begin(), queries.end(), cmp);
        sort(edgeList.begin(), edgeList.end(), cmp);

        makeDS(n);
        int i = 0;
        vector<bool> answer(queries.size(), false);
        for(vector<int>& query : queries){
            int limit = query[2];
            for(; i < edgeList.size() && edgeList[i][2] < limit; i++) join(edgeList[i][0], edgeList[i][1]);

            int x = query[0], y = query[1], originIdx = query[3];
            if(find(x) == find(y)) answer[originIdx] = true;
        }
        
        return answer;
    }
};

 

시간복잡도

 2중 for문이라 O(Q * E)가 나올 것 같지만, 실제로는 edgeList를 1번, queries를 1번 순회하며, edgeList를 순회하며 disjoint set을 union하기 때문에 O(Q + Elog*V)이다.

 

공간복잡도

 rank, parent vector는 size V, answer vector는 size Q이기 때문에 O(V + Q)이다.

 

후기

 나중에 다시 풀어보자... 어렵다.

 두 vertex의 연결 여부를 판단하기 위해서 union-find를 사용할 수 있다. 기억해 두자.