1. sweeping 개론
1) 스위핑이란?
스위핑이란 알고리즘 문제의 한 종류로, 한 번 등장하면 상당히 큰 인상을 남겼기에 여기서 소개한다. 스위핑은 보통 응용문제로 출제되어 다양한 알고리즘과 함께 사용되기에 난이도가 매우 높다. 여기서는 스위핑의 기초적인 부분에 대해서만 다룬다.
PS에서 스위핑sweeping이란 문자 그대로 한 번에 쓸어버리기 때문에 붙은 이름이다. 즉 주어진 데이터를 모종의 방법으로 전처리하여 한 번의 순회, O(N)에 해결하는 것을 목표로 한다. 엄밀히 따지자면 알고리즘이 아니며(마치 DP), 문제를 해결하기 위한 방법론에 가깝다.
일반적으로 전처리에는 정렬(sort)을 활용하는데, 속도가 빠른 quick sort를 사용한다. C++의 경우에는 template로 구현되어 뛰어난 범용성을 가지는 std::sort를 주로 사용한다.
개인적으로 sweeping은 그리디에 가깝게 느껴진다. 차이점이 있다면, sweeping에서는 greedy하게 접근할 수 있도록 주어진 데이터를 우리가 정렬해야만 한다.
2) 언제 적용할 수 있는가?
주어진 데이터들의 조합으로 구성되는 상태공간을 탐색해서 답을 찾아야 하는데, 그 데이터들이 선형으로 구성된다면, 즉 정렬이 가능해야 한다. 또한, 문제에서 요구되는 상태가 연속적인 영역을 구성하는 경우, sweeping이 상당히 적절할 것으로 생각된다. 따라서 각종 기하학과 함께 출제되는 경우가 많은 것으로 보인다.
2. 문제풀이 with C/C++
1) BOJ, 1689번: 겹치는 선분
해당 문제는 sweeping의 전형적인 예시로, 1차원 선분들에 대해서 가장 많이 겹치는 경우의 선분의 개수를 구하는 문제이다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using line = std::pair<int, int>; // 문제의 요구상태, 선분
// start, ascending order
// 좌측점, 우측점을 기준으로 오름차순 정렬함.
bool cmp_line_sort(const line& l1, const line& l2)
{
if (l1.first == l2.first)
return (l1.second < l2.second);
return (l1.first < l2.first);
}
// 우선순위큐의 우선순위를 결정하는 함수객체
// 우선순위큐는 현재 겹치는 선분들을 저장할 것임.
// 그렇기에 top에 가장 아슬아슬한, 가장 왼쪽에서 겹치는 선분이 위치함.
struct cmp_line_pq // minimum heap, second
{
bool operator()(const line& l1, const line& l2)
{
if (l1.second == l2.second)
return (l1.first > l2.first);
return (l1.second > l2.second);
}
};
std::vector<line> lines; // 입력받은 데이터들, 정렬의 대상, 탐색의 대상.
// 탐색 과정에서 중첩된 선분들을 저장할 우선순위 큐
std::priority_queue<line, std::vector<line>, cmp_line_pq> PQ;
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int N;
std::cin >> N;
lines.resize(N);
for (int i = 0; i < N; ++i)
{
std::cin >> lines[i].first >> lines[i].second;
}
// 스위핑을 수행하기 위해서 먼저 정렬을 수행함
std::sort(lines.begin(), lines.end(), cmp_line_sort);
// sweeping
int max_overlap = 0;
for (int i = 0; i < N; ++i)
{
while (!PQ.empty() && PQ.top().second <= lines[i].first)
{
PQ.pop();
}
PQ.push(lines[i]);
max_overlap = std::max(max_overlap, static_cast<int>(PQ.size()));
}
std::cout << max_overlap;
}
C++
복사
문제를 풀기 위해서 먼저 정렬을 수행했다. 선분은 두 점으로 표현이 가능하고, 이를 pair에 묶어서 line이라 정의했다. line의 정렬은 선 좌측점, 후 우측점을 기준으로 오름차순으로 수행했다. 즉 좌측점이 먼저 나올 수록 앞쪽으로 정렬되며, 같은 시작점을 가지는 경우에는 그 길이가 긴 선분, 우측점이 먼저 끝나는 선분이 앞으로 정렬된다.
또한 해당 문제에서는 우선순위큐를 도입했는데, 우선순위큐는 스위핑에 매우 잘 어울리기에 선호되는 조합이다. 해당 문제에서 우선순위큐는 지금까지 sweeping을 수행한 결과 겹쳐지는 영역의 선분을 저장한다. 해당 우선순위큐는 선 우측점, 후 좌측점에 대한 min heap으로, 우선순위큐는 현재 보유중인 원소 중 가장 우측점의 위치가 낮은 점을 가리킨다. 즉 top이 가리키는 선분은 항상 중첩 영역의 가장 좌측에서 겹치는 선분(가장 아슬아슬하게 중첩되어있는 선분)을 가리키고 있음을 알 수 있다.
스위핑 과정은 다음과 같다. 정렬된 선분들을 한 번만 탐색한다(이것이 스위핑의 정의이므로). 매 선분의 탐색 과정에서 현재 우선순위 큐의 top이 가리키는 선분과 비교를 수행한다. 비교는 현재 선분의 시작점과 top 선분의 우측 점을 비교하는데, 여기서 중첩 여부가 판정된다. 중첩이 발생하지 않았다면 top을 pop하고 이를 중첩이 발생하거나 큐가 빌 때 까지 반복한다. 이후 판정 결과와 별개로 선분을 push한다. 이후 최대 중첩 개수(max_overlap)의 값을 갱신한다.
여기까지가 sweeping의 기초다. 기회가 된다면 보다 응용된 문제에 대해서도 소개하고싶다.
