스위핑

스위핑에 대해 알아봅시다.

스위핑은 특정한 기준으로 자료들을 정렬하고, 이를 순서대로 탐색하며 문제를 해결하는 방식을 말합니다.

 

기법 자체는 매우 간단하지만, 특성상 다양한 자료구조와 결합해서 많이 쓰게 됩니다.

 

https://www.acmicpc.net/problem/2170

2170번: 선 긋기

 

가장 간단한 스위핑의 예시문제입니다.

수평선 위에 선분이 여러개 있는데, 선이 여러개 겹친 곳을 한 번씩만 계산했을 때 총 선의 길이의 합을 알아내야 합니다.

 

선분을 왼쪽 점이 증가하는 순으로 정렬합시다.

이를 차례대로 보면서, 현재 보고 있는 선분이 어디까지 이어져 있는지 갱신해 나가면 답을 쉽게 구할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
pll line[1000001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        ll x, y; cin >> x >> y;
        line[i] = { x,y };
    }
 
    sort(line, line + n);
 
    ll ans = 0;
    ll l = -1e9, r = -1e9; // 현재 선분의 왼쪽과 오른쪽 점을 관리한다.
    for (int i = 0; i < n; i++)
    {
        ll x = line[i].first;
        ll y = line[i].second;
 
        if (r < x)
        {
            ans += r - l;
            l = x, r = y;
        }
        else r = max(r, y);
    }
 
    ans += r - l;
    cout << ans;
}

 

위의 코드에서는 새로운 선분을 만날 때마다 끝점을 갱신해 줬지만,

미리 모든 선분의 시작점과 끝점을 모두 넣어놓고 정렬하여 답을 구할 수도 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
vector <pll> point;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        ll x, y; cin >> x >> y;
        point.push_back({ x, 0 });
        point.push_back({ y, 1 });
    }
 
    sort(point.begin(), point.end());
 
    ll ans = 0;
 
    int cnt = 0; // 현재 겹쳐진 선의 개수
    ll l = -1e9;
 
    for (auto it : point)
    {
        ll x = it.first;
        int t = it.second;
 
        if (t == 0)
        {
            if (cnt++ == 0) l = x;
        }
        else
        {
            if (--cnt == 0) ans += x - l;
        }
    }
 
    cout << ans;
}

---

https://www.acmicpc.net/problem/5419

5419번: 북서풍

 

전형적인 2차원 스위핑 문제입니다.

두 섬 사이를 x좌표가 감소하지 않고, y좌표가 증가하지 않는 방향으로 이동하여 움직일 수 있는 경우의 수를 구해야 합니다.

 

섬을 x좌표가 감소하는 순으로, 같다면 y좌표가 증가하는 순으로 정렬합시다.

이 순서대로 섬을 방문한다고 생각하면, 먼저 방문한 섬에서 나중에 방문한 섬으로 이동할 수 없다는 점은 자명합니다.

그리고 x좌표가 1순위로 정렬되기 때문에 x좌표는 신경쓰지 않아도 됩니다.

즉, 지금까지 방문된 섬 중에서 y좌표가 현재 섬보다 작거나 같은 점이 몇개인지만 세어 각각 더해 주면 된다는 사실을 알 수 있습니다.

 

점 갱신과 구간 쿼리를 사용하므로, 세그먼트 트리를 이용하면 구현할 수 있게 됩니다.

단, y좌표의 범위가 크기 때문에 좌표 압축이 필요합니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
pii point[75001];
vector <int> Y;
int getIdx(ll y) { return lower_bound(Y.begin(), Y.end(), y) - Y.begin() + 1; }
 
int segTree[75001];
void update(int idx, int val)
{
    while (idx <= n)
    {
        segTree[idx] += val;
        idx += idx & -idx;
    }
}
int getVal(int idx)
{
    int res = 0;
    while (idx)
    {
        res += segTree[idx];
        idx -= idx & -idx;
    }
    return res;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        Y.clear();
 
        cin >> n;
        for (int i = 1; i <= n; i++) segTree[i] = 0;
 
        for (int i = 0; i < n; i++)
        {
            ll x, y; cin >> x >> y;
            point[i] = { -x, y };
            // x좌표는 감소하는 순, y좌표는 증가하는 순 정렬
 
            Y.push_back(y);
        }
 
        sort(point, point + n);
 
        sort(Y.begin(), Y.end());
        Y.erase(unique(Y.begin(), Y.end()), Y.end()); // 좌표압축
 
        ll ans = 0;
        for (int i = 0; i < n; i++)
        {
            ll y = point[i].second;
            y = getIdx(y);
 
            ans += getVal(y);
            update(y, 1);
        }
 
        cout << ans << '\n';
    }
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

+ 요즘 많이 가입 신청이 들어오고 있습니다만, 꼭 그룹에 가입하셔서 제 문제들을 푸실 필요는 없습니다.

solved.ac 에서 태그를 찾아 푸시거나 백준 단계별로 풀기 에서 문제를 찾아 푸셔도 충분합니다!

그룹은 단순히 제 개인용 알고리즘 문제집 정리 용도이니 참고해주세요!

https://www.acmicpc.net/group/7712

ANZ1217