[Sweeping] BOJ 3392 화성 지도

문제 링크 : www.acmicpc.net/problem/3392

3392번: 화성 지도

스위핑(Sweeping) 알고리즘으로 해결할 수 있는 대표적인 유형의 문제이다.

스위핑 알고리즘을 간단히 말하자면, 일련의 자료들을 순서대로 한 번 훑으며 정답을 구하는 방법이라 할 수 있다.

개념이 가벼운 만큼 응용된 문제는 꽤 어려운 축에 속한다.

 

아무튼 이 문제를 스위핑 알고리즘으로 해결하기 위해 다음과 같은 예제를 풀어보자.

우리는 이 직사각형들의 세로변만을 뽑아내어 정렬할 것이다.

각 세로변들을 x좌표에 대해 오름차순으로 정렬한 후, 이를 한 번만에 훑으며 문제를 해결해 보자.

해결 과정은 다음과 같다.

① 맨 처음 수직선에 대해, 해당 수직선이 포함하는 y좌표 범위의 cnt를 1씩 증가시킨다.

② 현재 cnt가 1 이상인 y의 개수를 세어, 이전 수직선과의 x좌표 차이만큼 곱해 정답에 더한다.

③ 현재 수직선이 직사각형의 시작 수직선(왼쪽 세로변)이라면 포함하는 y좌표 범위의 cnt를 1 증가시킨다.

만약 끝 수직선(오른쪽 세로변)이라면 cnt를 1 감소시킨다.

④ ② - ③의 과정을 마지막 수직선까지 반복한다.

 

첫 번째 세로변은 x좌표가 10이고, 커버하는 y좌표의 범위가 10-20인 수직선이다.

이 수직선은 직사각형의 시작하는 수직선이므로, 10 - 20의 y에 대해 cnt를 1 증가시킨다.

두 번째 수직선은 x좌표가 15이고, 포함하는 y좌표가 15-30인 시작 수직선이다.

우선 현재 cnt가 1인 y좌표의 개수를 센다. 이는 그림에서 빨간색으로 칠해진 구간과 같다. 즉, 10이다.

이 값과 이전 수직선과의 x좌표 차이를 곱해 정답에 더한다. (현재까지 정답 : 5 * 10 = 50)

두 번째 수직선은 시작 수직선이었으므로, 포함하는 y 범위의 cnt를 1 증가시킨다.

15-20 구간의 cnt는 현재 2임에 주의하자.

3번째 수직선은 x좌표가 20이고 포함하는 y좌표가 10-20인 끝 수직선이다.

우선 현재 cnt가 1인 y좌표의 개수를 센다. 이는 그림에서 빨간색 및 파란색으로 칠해진 구간과 같다. 즉, 20이다.

(cnt값이 1을 넘어가더라도 이를 한 번으로만 세어야 함에 주목하자.)

이 값과 이전 수직선과의 x좌표 차이를 곱해 정답에 더한다. (현재까지 정답 : 50 + 20 * 5 = 150)

세 번째 수직선은 끝 수직선이었으므로, 포함하는 y범위의 cnt를 1 감소시킨다.

마지막 수직선은 x좌표가 20이고, 포함하는 y좌표가 15-30인 끝 수직선이다.

우선 현재 cnt가 1인 y좌표의 개수를 센다. 이는 그림에서 빨간색으로 칠해진 구간과 같다. 즉, 15이다.

이 값과 이전 수직선과의 x좌표 차이를 곱해 정답에 더한다. (현재까지 정답 : 150 + 5 * 15 = 225)

 

이 문제를 구현할 때에는 각 y좌표 구간들에 대한 cnt 여부를 파악하기 위해 세그먼트 트리를 활용한다.

세그먼트 트리(Segment Tree)

하지만 위의 문제풀이 과정에서 주목해야 할 점이 있었다. 바로, cnt의 값이 2 이상이더라도 1로 세어야 한다는 점이었다.

이를 구현하기 위해 우리는 두 개의 세그먼트 트리를 활용한다. 하나는 cnt, 하나는 segtree이다.

cnt 트리의 노드는 그 노드가 표현하는 구간의 cnt를 나타낸다. 예를 들어, 4-15 구간을 나타내는 노드의 cnt가 1이라면, 4에서 15까지의 모든 y좌표의 cnt값이 1이라는 것을 의미한다.

segtree 트리의 노드는 그 노드가 표현하는 구간의 cnt가 1 이상인 y좌표의 개수를 나타낸다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
#define MAXSIZE    30002
 
using namespace std;
typedef pair<int, int> p;
typedef long long ll;
 
typedef struct {
    int x;
    p y;
    bool start = false;
}vert;
 
int n;
int segtree[MAXSIZE * 4];
int cnt[MAXSIZE * 4];
vector<vert> verts;
 
void update_range(int node, int start, int end, int l, int r, int val) {
    //벗어나는 범위
    if (start > r || end < l) return;
 
    //포함되는 범위
    if (l <= start && end <= r) {
        cnt[node] += val;
    }
    else {
        //걸치는 범위
        int mid = (start + end) / 2;
        update_range(node * 2, start, mid, l, r, val);
        update_range(node * 2 + 1, mid + 1, end, l, r, val);
    }
 
    if (cnt[node]) segtree[node] = end - start + 1;
    else {
        if (start == end) segtree[node] = 0;
        else segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
    }
}
 
int get_answer() {
    int ret = 0;
    int diff_x = 0;
    for (int i = 0; i < verts.size(); i++) {
        if (i > 0) {
            diff_x = verts[i].x - verts[i - 1].x;
            ret += diff_x * segtree[1];
        }
        int val = verts[i].start == true ? 1 : -1;
        update_range(1, 1, MAXSIZE, verts[i].y.first, verts[i].y.second - 1, val);
    }
 
    return ret;
}
 
vert create_vert(int x, int y1, int y2, bool start) {
    vert temp;
    temp.x = x; temp.y = { y1, y2 }; temp.start = start;
    return temp;
}
 
bool compare(vert a, vert b) {
    return a.x < b.x;
}
 
void init() {
    int x1, x2, y1, y2;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        verts.push_back(create_vert(x1, y1 + 1, y2 + 1, true));
        verts.push_back(create_vert(x2, y1 + 1, y2 + 1, false));
    }
 
    sort(verts.begin(), verts.end(), compare);
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    int answer = get_answer();
    printf("%d\n", answer);
 
    return 0;
}

 

29번째 줄은 현재 구간이 우리가 갱신하려는 구간에 완전히 포함된다면 현재 구간을 나타내는 구간의 cnt값을 증감시킨다는 것을 의미한다.

만약 33번째 줄부터 시작하는 절처럼 걸치는 구간인 경우는 절반의 구간에 대해 재귀한다. 즉, 24 ~ 36번째 줄까지는 cnt 트리에 대한 연산이다.

38번째 줄은 현재 노드가 나타내는 구간이 갱신하려는 구간에 완전히 포함될 때 segtree 값을 갱신하는 부분이다.

만약 4-15 구간을 나타내는 노드의 cnt가 1 이상이라면, 각 좌표의 cnt값에 상관없이 (15 - 4 + 1) = 12개의 y좌표만을 세어 준다.

39번째 줄처럼 걸치는 구간이라면 segtree의 양 자식 노드의 값을 더한다. 만약 리프 노드라면, 그 값은 0이 된다.