C++ 스위핑 알고리즘 (C++ Sweeping, BOJ 2170, BOJ 15922)

스위핑 알고리즘은 이름 그대로 한 쪽 방향으로 쓸고 가면서 데이터를 처리하는 기법입니다.

 

정렬된 데이터들에 대해 주로 단일 방향으로 스캔해가면서 계산을 처리해주는 방식으로 문제를 풉니다.

어려운 문제들을 보면 2차원 평면에서 스위핑 알고리즘이 구현되기도 하는데, 이 경우 데이터 수가 많기 때문에 세그먼트 트리와 같은 자료구조를 병합하여 사용하는 것 같습니다.

(이 포스트는 제가 정리해놓고 나중에 다시 보려고 쓰는 거라 고차원 스위핑 문제에 대해서는 풀이를 해보고 나서 다시 정리하겠습니다.)

 

백준(BOJ)에는 스위핑 알고리즘으로 분류된 문제가 300문제 정도가 있는데 이것으로 미루어보아 엄청 빈출되는 유형은 아니지만 은근히 자주 사용되는 알고리즘으로 보입니다.

 

 

백준 BOJ 2170번 : 선 긋기

 

만약 위의 문제에서 x, y의 범위가 -10000 ~ 10000 정도였다면 bool 변수의 크기를 2만개 이상으로 설정하여 풀이해줄 수 있습니다.

그러나 이와 같이 범위가 굉장히 큰 경우에는 별개의 선분에 대한 범위의 연산으로 처리할 수 밖에 없습니다.

 

이전 선분의 양 끝 점의 좌표를 저장해준 뒤 다음 선분의 시작점이 이전 선분의 오른쪽 끝 점 이전에 걸치는 경우 중복되지 않는 부분만의 길이를 더하여 길이를 갱신해 줄 수 있습니다. (만약 겹치지 않는 경우 선분 길이를 그대로 더하고 양 끝 점의 좌표만 갱신)

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<pair<int, int>> v(N);
    for(int i=0; i<N; i++) cin >> v[i].first >> v[i].second;

    sort(v.begin(), v.end());

    int ans = 0, l = INT_MIN, r = INT_MIN;
    for(int i=0; i<N; i++) {
        if(v[i].first > r) {
            ans += r - l;

            l = v[i].first;
            r = v[i].second;
        }
        else r = max(r, v[i].second);
    }
    ans += r - l;

    cout << ans << "\n";
}

 

따라서 위와 같이 풀이를 해줄 수 있습니다.

당연하지만 스위핑 알고리즘을 구현하기 위해서는 반드시 데이터들이 정렬되어 있어야 합니다.

 

 

백준 BOJ 15922번 : 아우으 우아으이야!!

 

위의 문제와 완전히 동일한 문제입니다.

풀이 코드도 완전히 동일합니다.