> 스위핑 기법(Sweeping Algorithm)
이번에 소개해 드릴 기법은 스위핑 알고리즘(sweeping algorithm)이라고 하는데, 기법 개념 자체는 굉장히 간단하고 범용적인 대신에,
대부분 겁나게 어렵습니다. 기본적으로 다른 기법이나 자료구조와 반드시 얽힙니다.
스위핑이라는 건 그냥 어떤 선이나 공간을 한쪽에서부터 싹 쓸어버린다는 건데
한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 뭔가를 해 주면 정답이 구해지는 형태입니다.
- BOJ[2170] : 선 긋기
https://www.acmicpc.net/problem/2170
[
2170번: 선 긋기
첫째 줄에 선을 그은 횟수 N(1≤N≤1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점이 주어진다. 선택한 지점은 -1,000,000,000 이상 1,000,000,000 이하의 정수이다.
](https://www.acmicpc.net/problem/2170)
수평선 위에 선분을 여러 변 긋는데, 모든 선분을 긋고 나서 수평선 위에 덮인 구간 길이 총합을 구하라는 문제입니다.
당연히, 좌표가 20억 1개 구간이고 선이 백만 개니까 20억 1개 칸 배열을 만들고 무슨 짓을 하는 건 안 됩니다.
일단 예제를 그림으로 나타내면 이와 같고, 답은 5가 됩니다.
이때, 구간이 2군데로 분리되어 나타내어지는 것을 볼 수 있고 각 길이가 4, 1이죠. 결과는 이들의 합 5고요.
이제 우리는 만약 이어졌거나 겹치는 선분들끼리 아예 한 구간으로 합쳐서, 마지막에 최종적으로 다 합쳐지고 남은 구간들의 길이만 세서 더하면 되지 않을까 하는 생각을 해봅니다.
그걸 쉽게 하려면 어떻게 해야 할까요?
제일 먼저 시작하는(왼쪽 끝점 좌표가 작은) 선분부터 순회하면 됩니다.
예제의 경우 [1, 3], [2, 5], [3, 5], [6, 7]의 순서대로 순회하면 됩니다.
이제부터 선분들을 순회하면서, 현재의 구간을 이어붙일 수 있는 한 최대한 이어붙이다가
더 이어붙일 수 없으면 이번 구간의 길이를 결과에 더하는 식으로 알고리즘을 수행할 겁니다.
따라서 순회하면서 가지고 있어야 하는 정보는 현재 순회할 선분 번호, 현재 구간의 시작 좌표입니다.
먼저 첫 번째 선분은, 뭐... 첫 번째니까 현재 구간이 자신으로 초기화됩니다.
현재 구간은 [1, 3]이 됩니다.
두 번째 선분 [2, 5]를 순회하면, 현재까지의 구간과 이번 선분이 겹치거나 이어져 있으므로 합칠 수가 있습니다!
현재 구간은 [1, 5]가 됩니다.
세 번째 선분 [3, 5]는 이미 현재 구간에 포함이 됩니다. 현재 구간은 변함이 없습니다.
네 번째 선분 [6, 7]을 봅시다. 이제 이번 선분과 현재 구간은 절대 합칠 수가 없습니다.
이때는 현재 구간이 [1, 5]니까 그 길이 4를 결과에 더하고, 구간을 다시 이번 선분인 [6, 7]로 초기화합니다.
모든 선분을 다 순회하고 나서도, 마지막에 남은 구간 [6, 7]의 길이 1도 결과해 더해 줘야 합니다.
이렇게 결과는 4+1 = 5가 됩니다.
지금 이렇게 한 번 더 합칠 수 없게 된 구간은 더 이상 절대 합쳐질 수 없는 이유가 선분을 왼쪽 끝 좌표 순서대로 순회했기 때문입니다.
왼쪽 끝 좌표가 같으면 어떤 것부터 순회해야 할까요? 그때는 아무 상관이 없다는 것을 어렵지 않게 알 수 있습니다.
현재 구간과 이번 선분이 합쳐질 수 있느냐의 여부를 결정하는 것은 이번 선분의 왼쪽 끝 좌표이기 때문입니다. 따라서 왼쪽 끝 좌표가 같은데 어떤 건 합쳐지고 어떤 건 합쳐지지 않거나 하여 순서에 따라 결과가 달라지는 일은 있을 수 없습니다.
따라서 이 알고리즘의 형태를 다르게 표현하면, 수평선의 왼쪽 끝에서부터 훑다가 마주치는 선분이 있으면 뭔가 처리를 해 주는 식으로 말할 수 있습니다.
따라서 이 알고리즘을 완수하려면 선분을 왼쪽 끝 좌표순으로 정렬하여 순회하면 됩니다.
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
const int INF = 1e9+1;
int main(){
int N;
scanf("%d", &N);
P L[1000000];
for(int i=0; i<N; i++){
int s, e;
scanf("%d %d", &s, &e);
L[i] = P(s, e);
}
// 선분들을 왼쪽 끝 좌표 순으로 정렬
sort(L, L+N);
// [l, r]: 현재 합치고 있는 구간
int result = 0, l = -INF, r = -INF;
for(int i=0; i<N; i++){
// 현재 구간과 이번 선분이 합쳐질 수 없음
if(r < L[i].first){
// 결과에 더함
result += r-l;
// 현재 구간을 이번 선분으로 초기화
l = L[i].first;
r = L[i].second;
}
// 합쳐짐: 현재 구간의 r을 늘릴 수 있으면 늘림
else r = max(r, L[i].second);
}
result += r-l; // 마지막 구간도 결과에 더해 줌
printf("%d\n", result);
}소스 코드는 위와 같습니다.
위 문제는 수평선 하나만을 훑지만, 아예 2차원 평면을 쭉 훑는 경우도 있습니다.
이때는 대체로 평면을 하나의 수평선이나 수직선으로 훑으면서 마주치는 점, 선, 다각형 등의 도형을 차례차례 처리해 주는 형태를 띄게 됩니다.
물론 난이도는 1차원이었을 때보다 높은 편이고, 자료구조가 정말 중요합니다.
- BOJ[5419] : 북서풍
https://www.acmicpc.net/problem/5419
[
5419번: 북서풍
각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다.
](https://www.acmicpc.net/problem/5419)
이 문제에서는, 2차원 평면 안의 점들 중 x좌표가 같거나 커지고, y좌표가 같거나 작아지는 점 쌍이 몇 개나 되는지를 구하라고 합니다.
당연히, O(N^2) 브루트포스가 먹힐 리는 없죠. 75000*75000은 시간 안에 절대 불가능한 수치입니다.
이걸 스위핑으로 어떻게 풀 수 있을까요? 아이디어는 이러합니다.
만약 y축에 평행한 수직선을 제일 왼쪽 끝에서부터 제일 오른쪽 끝으로 훑으면서 마주치는 점들마다 이 점으로 항해할 수 있는 점의 개수를 센다고 해 봅시다. 이번에 마주친 점을 P라고 해보죠.
쉽게 생각하기 위해 x좌표가 같은 점은 없다고 하면, P로 항해 가능하려면 반대편 점은 이미 수직선과 마주쳤어야 합니다. 그래야 항해하면서 x좌표가 커지죠?
따라서, 지금까지 수직선과 마주쳤던 점들, 즉 x좌표가 P의 것보다 작은 점들 중에서 y좌표는 P의 것보다 크거나 같은 점의 개수를 세서 결과에 더하면 됩니다.
그럼 이제 문제를 좀 더 어렵게 해서, x좌표가 같은 점들이 존재할 수 있다면 x좌표가 같은 점들 중에서는 어떤 것을 먼저 방문하면 좋을까요?
y좌표가 큰 것부터 방문하는 게 좋습니다. 그렇다면 x좌표가 같은 점 두 개를 P, Q라 하고 P.y > Q.y라 하면 P->Q로만 항해가 가능하니까, Q를 방문할 때 P를 이미 방문한 상태인 게 구현하기 좀 더 쉬울 것 같지요?
이러한 문제가 있다고 해 봅시다. 이제 수직선을 왼쪽에 두고 시작해 오른쪽으로 훑으면서 마주치는 점들마다 자신으로 항해 가능한 다른 점의 개수를 셀 것입니다.
먼저 제일 왼쪽에 있는 점을 마주쳤습니다.
이걸 첫 번째로 방문했으니 당연히... 이 점으로 항해할 수 있는 다른 점은 없겠죠.
두 번째로 마주친 점은, 방금 첫 번째 점에서 항해해올 수 있습니다.
그러므로 결과에 1을 더합니다.
세 번째 점은 역시 첫 번째 점에서 도달 가능하므로 결과 +1.
자 이번엔 x좌표가 같은 두 개의 점을 만났습니다.
약속대로 y좌표가 큰 녀석부터 방문합시다. 이 점으로 항해할 수 있는 점은 없습니다.
바로 아래의 점은, 자신과 x좌표가 같거나 y좌표가 같은 점까지 포함해 총 3곳에서 항해해올 수 있습니다.
이때, y좌표가 더 큰 점을 미리 방문했기에 아직까지도 이번 점으로 항해할 수 있는 점은 이미 방문한 점들 중에만 있다는 법칙이 깨지지 않은 겁니다.
여섯 번째 점.
대망의 마지막 점. 이렇게 매번 항해 가능한 점 개수를 세서 더하면 결과가 되는데요.
자 그럼, 도대체 어떻게 빠른 시간 안에 반대편 점의 개수를 셀까요?
지금까지 과정을 돌이켜보면 우리가 센 점의 개수는 이미 방문한 점들 중에서 현재 점보다 크거나 같은 y좌표를 가진 점의 개수입니다.
조금만 더 힌트를 드리기 위해 말을 변형시켜 보면, 이미 방문한 점들 중에서 구간 [P.y, ∞]에 속하는 y좌표를 가지는 점의 개수입니다.
정답은 세그먼트 트리입니다.
점이 최대 75000개니까, 서로 구분되는 y좌표의 개수는 최대 75000개일 것이므로 각 y좌표마다 0~74999 사이로 재설정하는 과정을 거친 후, 각 y좌표마다 대응하는 (75000개의) 리프 노드를 가진 세그먼트 트리를 만듭니다.
수직선으로 점들을 훑으면서 일단 구간 [P.y, MAX_Y]의 합을 결과에 더하고(자신으로 항해 가능한 점의 개수를 세는 과정),
자신의 y좌표에 해당하는 칸을 +1하는 식으로 구현하면 알고리즘을 구현할 수가 있게 됩니다!
#include <cstdio>
#include <algorithm>
using namespace std;
const int SIZE = 1<<18; // 75000*2 이상
typedef pair<int, int> P;
// 세그먼트 트리 구조체
struct SegTree{
int arr[SIZE];
SegTree(){ fill(arr, arr+SIZE, 0); }
// n번째 리프 노드를 1 증가시킴
void inc(int n){
n += SIZE/2;
while(n > 0){
arr[n]++;
n /= 2;
}
}
// 구간 [s, e)의 합
int sum(int s, int e){ return sum(s, e, 1, 0, SIZE/2); }
int sum(int s, int e, int node, int ns, int ne){
if(e <= ns || ne <= s) return 0;
if(s <= ns && ne <= e) return arr[node];
int mid = (ns+ne)/2;
return sum(s, e, node*2, ns, mid) + sum(s, e, node*2+1, mid, ne);
}
};
int main(){
int T;
scanf("%d", &T);
for(int t=0; t<T; t++){
SegTree ST;
int N, range = 0;
P p[75000];
scanf("%d", &N);
for(int i=0; i<N; i++){
int x, y;
scanf("%d %d", &x, &y);
p[i] = P(x, y);
}
// 점들을 y좌표 순으로 정렬
sort(p, p+N, [](P &a, P &b){
return a.second < b.second;
});
// 서로 구분되는 y좌표 개수를 세며 y좌표 재설정
int newY[750000];
for(int i=0; i<N; i++){
if(i>0 && p[i].second != p[i-1].second) range++;
newY[i] = range;
}
for(int i=0; i<N; i++)
p[i].second = newY[i];
// 점들을 다시 x좌표 순으로, x좌표가 같다면 y좌표가 작아지는 순으로 정렬
sort(p, p+N, [](P &a, P &b){
if(a.first == b.first) return a.second > b.second;
return a.first < b.first;
});
// 점들을 차례대로 훑으면서 이 점으로 항해할 수 있는 점 개수 세기
long long result = 0;
for(int i=0; i<N; i++){
result += ST.sum(p[i].second, SIZE/2);
ST.inc(p[i].second);
}
// 결과 출력
printf("%lld\n", result);
}
}휴 이제 한 문제 끝났는데요... 보통이 아닌 일이네요.
스위핑 알고리즘은... 사실 그냥 훑기만 한다면 어디든지 갖다붙이기 정말 좋은 단어이고,
실상은 알고리즘 종류부터 구현해야 하는 방법이나 필요한 자료구조까지 모든 게 너무나도 천차만별인 굉장히 포괄적인 개념.
다만, 훑는다는 개념이 도형들을 일정 기준에 맞춰 정렬해 놓고 순서대로 훑는 것과 동치가 되는 경우가 절대 다수입니다. 이런 공통점이 있습니다.
- BOJ[3392] : 화성 지도
https://www.acmicpc.net/problem/3392
[
3392번: 화성 지도
첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30
](https://www.acmicpc.net/problem/3392)
이 문제도 정말 정말 유명한 스위핑 문제 중 하나입니다.
존재하는 직사각형들의 합집합 영역의 넓이를 구하라는 건데요.
이번에도 한번 y축과 평행한 수직선으로 평면을 왼쪽에서 오른쪽에서 훑어봅시다.
구현 난이도에 상관없이 그냥 생각하기는 제일 쉬운 스위핑 풀이는 이것입니다.
y좌표가 0 이상 30000 이하이므로 30000개의 크기 1인 구간으로 나눠서 생각하기로 합시다.
① 각 직사각형마다 세로변 2개씩을 추출한다. 둘 중 하나는 시작하는 세로변(x좌표가 작음), 하나는 끝나는 세로변이다. 이들을 x좌표 순으로 정렬하고 순서대로 훑으면서 ②③을 수행한다.
② 바로 전에 훑은 세로변과의 x좌표 차를 dx라 하자. 현재 y좌표 구간들 중 1 이상의 값을 가진 칸의 개수를 센 뒤 dx와 곱해서 결과에 더한다.
③ 이번 세로변이 시작하는 세로변이면, 세로변 안에 속하는 y좌표 구간들에 1을 더한다. 끝나는 세로변이면, 구간들에 1을 뺀다.
어떻게 제일 쉬운 게 이 따위냐
대충 이해는 가시리라고 믿습니다.
③을 수행하기 위해서는 최소한 레이지 프로퍼게이션을 도입한 세그먼트 트리는 필요할 것 같은데, 정말 다행히도 그냥 세그먼트 트리만으로도 문제를 풀 수는 있습니다.
②의 경우 dx를 곱하는 것이 자연스러운 과정이고, 의도한 바는 아니지만 이 행위가 x좌표가 같은 세로변 중에서는 어떤 것을 먼저 방문하더라도 결과가 같게 해 줍니다. 똑같은 x좌표의 세로변들을 연속해서 훑는 중에는 dx가 0이 되어서 결과엔 변함이 없기 때문이죠.
이러한 문제가 있다고 하면
이렇게 구간을 쪼갤 수 있습니다. 자세한 과정은 생략합니다.
이 문제를 풀기 위한, 레이지 프로퍼게이션이 없는 세그먼트 트리는 사실... 조금 복잡합니다. 사람에 따라서 레이지 프로퍼게이션을 그냥 쓰는 게 더 쉬워 보일 수도. 그래도 검색해 보시면 나올 겁니다.
소개드린 문제가 다들 세그먼트 트리를 쓰고 있는데, 2차원 평면에서 행하는 스위핑 알고리즘은 세그먼트 트리와 아주 죽이 잘 맞습니다. 항상 도형을 만날 때마다 지금까지 방문한 것들 중 ~~의 개수, 합 같은 것을 체크하기 때문이죠.
물론, 세그먼트 트리가 아닌 다른 걸 쓰는 경우도 절대 없지는 않은데 밑의 추천문제에서 만나보세요(?).
스위핑 관련 추천 문제
2170번: 선 긋기
위에서 설명한 문제입니다.
2836번: 수상 택시 (★)
먼저, M이 문제에 등장하는 모든 집들 중 가장 큰 번호를 가진 경우부터 생각해 봅시다. 이때는 어떻게 문제를 풀어야 할까요?
일단 태울 수 있는 사람 수에 제한이 없으니까, 오른쪽으로 가는 사람들은 그냥 0->M번 집으로 가기만 하면 저절로 다 도착하게 됩니다.
문제는 왼쪽으로 가는 사람들인데, 어떻게 해야 가능한 한 효율적으로 움직일 수 있을까요?
답은 선 긋기 문제와 비슷합니다. 4->2, 3->1번 집으로 가는 사람이 있다고 해 봅시다. 이때는 0->4->2->3->1->M으로 한 명씩 조달(?)하면서 움직이는 것보다, 0->4->1->M으로 한번에 움직이는 게 훨씬 빠릅니다.
즉, 왼쪽으로 가는 사람들의 시작점과 도착점으로 구간들을 만들었을 때 두 구간이 합쳐질 수 있으면 합쳐진 구간만 한번에 돌아가는 게 제일 빠르단 거죠.
이렇게 해서 선 긋기 문제처럼 합칠 수 있는 한 최대한 구간들을 합쳐서, 그 구간들만큼 돌아갔다가 와야 하므로 M + (구간 길이 합)*2가 답이 됩니다.
그럼 좀 더 어려운 경우인, M보다 큰 번호의 집이 문제에 등장할 때는?
문제에 등장하는 가장 큰 번호의 집을 K번이라고 해 봅시다. 이때 일단 반드시 K번 집은 가야 하므로, 0->K->M번 집으로 가는 경로로 움직이고 시작합시다. 이러면 오른쪽으로 가는 사람들은 반드시 도착하게 되고, 왼쪽으로 가는데 목적지가 M번 이상인 집인 사람들도 반드시 도착하게 됩니다.
이제 아직도 도착하지 못한 사람들, 즉 왼쪽으로 가면서 목적지 집 번호가 M보다 작은 사람들만 태우면 되는데, 역시 위와 비슷하게 문제를 풀 수 있습니다.
10000번: 원 영역 (★)
원을 왼쪽 시작 좌표 순으로, 이게 같다면 반지름이 큰 걸 먼저 오도록 정렬한 후 훑습니다.
훑으면서 원을 스택에 쌓아 나가는데, 그 전에 자신을 포함하지 않는 원이 스택 top에 있는 한 전부다 pop합니다.
기본적으로 원이 하나 있을 때마다 영역 개수는 반드시 1개 늘어나는데, 1개가 더 늘어날 경우는 어떤 원 안에 있는 원들이 자신의 안쪽을 양분할 경우입니다. 이걸 각 원마다 판별해서 원이 pop될 때마다 경우에 따라 결과를 추가로 1 증가시켜야 합니다. 구현이 어려운 문제.
5419번: 북서풍
위에서 설명한 문제입니다.
3392번: 화성 지도 (★)
위에서 설명한 문제입니다.
10534번: City Park (★)
인접해 있는 직사각형 뭉치들 중 그 넓이 합이 제일 큰 걸 구하라고 합니다. 놀랍게도 한 모서리에서만 접촉해도 인접한 걸로 치네요.
이 문제는 상당히 어려운데, 일단 인접한 두 직사각형을 하나로 합치며 넓이도 합치는 것은 유니온 파인드를 사용해서 구현할 수 있지만, 인접 여부는 어떻게 판별하죠?
인접 여부는 두 직사각형의 가로나 세로변끼리 만나는 경우로 생각할 수 있습니다. 가로변이 겹치는 경우는 두 변의 y좌표가 같고, 두 변의 시작~끝 x좌표로 구간을 나타냈을 때 두 구간이 인접하거나 겹치면 됩니다. 세로변도 비슷하고요.
문제가 어려운 이유는 어떻게 가로변 겹침 여부와 세로변 겹침 여부를 다 판단할지를 모르겠어서입니다.
일단 세로변끼리 겹치는 놈들끼리만이라도 합쳐봅시다. 먼저 직사각형마다 세로변 2개를 추출해서 이 세로변들을 x좌표 순, x좌표가 같으면 세로변의 두 y좌표 중 작은 y좌표 순으로 정렬합니다. 이때 세로변마다 자신이 몇 번째 직사각형에 속해있는지를 저장하고 있으면 편할 겁니다.
y축에 평행한 수직선을 2차원 평면에 훑으면서 스위핑해 봅시다. 이것은 세로변을 위에서 정렬한 순서대로 훑는 것과 동일합니다. 이때 x좌표 같은 세로변들끼리 구간이 겹치면 양쪽 직사각형을 합치는 식으로 구현이 얼추 가능합니다.
그럼 가로변끼리 겹치는 놈들은 어떻게 합치죠? 사실... 해답은 의외로 간단합니다. 스위핑을 2번 하는 겁니다. 세로변에 대해 한 번, 가로변에 대해 한 번. 이렇게 스위핑을 2번 하면 합쳐질 놈들끼리는 다 합쳐지게 됩니다.
'알고리즘 > [ 개념 ]' 카테고리의 다른 글
| [ 개념 ] 49. LCS(Longest Common Subsequence) (0) | 2021.03.29 |
|---|---|
| [ 개념 ] 48. 트라이(Trie).ver2 (2) | 2020.09.25 |
| [ 개념 ] 46. 레이지 프로퍼게이션(Lazy Propagation) (0) | 2020.09.22 |
| [ 개념 ] 45. 볼록 껍질(Convex Hull) (0) | 2020.09.22 |
| [ 개념 ] 44. 이분 매칭(Bipartite Matching) (2) | 2020.09.17 |