LeetCode 1697. Checking Existence of Edge Length Limited Paths

문제

leetcode.com/problems/checking-existence-of-edge-length-limited-paths/

Checking Existence of Edge Length Limited Paths - LeetCode

풀이과정

그래프의 정점 수 |V| <=10^5, 간선 수 |E| <= 10^5, 쿼리 수 |Q| <=10^5 이다.

최악의 경우에도 간선 수의 상한이 정점 수 의 상한과 같은 굉장히 sparse한 그래프의 특징을 가지게 된다.

가장 먼저 떠오른 솔루션은 Floyd-Warshall algorithm을 이용하는 것인데 O(V^3)은 가능성이 없다.

Dijkstra's algorithm도 쿼리당 O(V log V)가 필요한데, 쿼리의 수가 10^5 이므로 그냥은 안된다.

문제의 조건을 다시 검토해 보면, 간선의 가중치는 쿼리에서 주어진 limit 조건을 만족하는지만 검사하는데 쓰이고 그 후에는 관여하지 않는다. 즉 문제는 두 정점 간 최단거리를 찾는 것이 아니라, 두 정점간 연결성을 묻고 있다. limit 조건은 에지를 사용할 수 있는지 없는지, 즉 에지의 유무를 결정한다.

주어진 limit에 대해서 사용 가능한 edge만들 이용하여 graph를 구성 한다고 했을 때, 이 그래프는 몇 개의 connected component들로 구성된 것이다. 쿼리에서 주어진 정점 p와 q가 같은 component에 속하면 true, 그렇지 않으면 false를 반환하면 된다. 그래프가 undirected이므로, disjoint set으로 쉽게 구현 할 수 있다. 

문제는 쿼리의 수가 10^5개 라는 것인데, 여기에서 쿼리가 offline이라는 것과 1707번 문제의 회고가 내 머리를 스쳤다.

ilyoan.tistory.com/entry/LeetCode-1707-Maximum-XOR-With-an-Element-From-Array

LeetCode 1707. Maximum XOR With an Element From Array

쿼리를 limit순으로 정렬을 하면 disjoint set을 빌드업을 해 나가는 과정에서 쿼리에 대한 답을 줄 수 있다. 왜냐하면 limit보다 값이 큰 간선은 어차피 사용하지 않을테니 disjoint set에 넣을 필요가 없고 limit보다 값이 작은 간선은 이미 disjoint set에 반영이 되어 있기 때문이다.

솔루션

struct DisjointSet {
    s: Vec<usize>,
    r: Vec<usize>,
}

impl DisjointSet {
    pub fn new(n: usize) -> Self {
        Self {
            s: (0..n).collect::<Vec<_>>(),
            r: vec![0; n]
        }
    }
    pub fn find(&mut self, x: usize) -> usize {
        if self.s[x] != x {
            self.s[x] = self.find(self.s[x]);
        }
        self.s[x]
    }
    pub fn union(&mut self, x: usize, y: usize) {
        let sx = self.find(x);
        let sy = self.find(y);
        if sx == sy {
            return;
        }
        let (sh, sl) = if self.r[sx] > self.r[sy] {
            (sx, sy)
        } else {
            (sy, sx)
        };
        self.s[sl] = sh;
        if self.r[sh] == self.r[sl] {
            self.r[sh] += 1;
        }
    }
}

impl Solution {
    pub fn distance_limited_paths_exist(n: i32, edge_list: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<bool> {
        let mut ds = DisjointSet::new(n as usize);
        let mut es = edge_list.into_iter().map(|e| {(e[2], e[0], e[1])}).collect::<Vec<_>>();
        es.sort();
        let mut qs = queries.into_iter().enumerate().map(|(qi, q)| {(q[2], q[0], q[1], qi)}).collect::<Vec<_>>();
        qs.sort();
        let mut ei = 0;
        let mut res = vec![false; qs.len()];
        for (limit, p, q, qi) in &qs {
            while (ei < es.len()) {
                let (dis, u, v) = &es[ei];
                if dis >= limit {
                    break
                }
                ds.union(*u as usize, *v as usize);
                ei += 1;
            }
            res[*qi as usize] = ds.find(*p as usize) == ds.find(*q as usize);
        }
        return res;
    }
}

회고

회고 1

1707번 문제와 비슷하게 query가 offline이라는 특징을 활용하는 문제였다. 1707번과 다른 점은, 1707번이 query의 offline 특징을 문제의 단순화와 최적화에 활용할 수 있었던 반면, 이 문제는 이 특성을 적극 활용하지 않으면 다른 풀이 방법이 없는 것 처럼 보인다.

query가 offline으로 주어진 문제의 경우 query을 정렬하는 등의 조작을 하여 문제를 단순화하는 기법이 있다는 것을 하나의 패턴으로 염두해두고 있을 필요가 있을 것 같다.

회고 2

Rust 문법에 다시 익숙해 지고자 문제를 rust로 풀었는데, 역시나 많은 부분이 어색하다. 컴파일러를 만족시키는데 꽤 많은 시간을 들여야 했다.