Line Sweeping

라인 스위핑(Line Sweeping) 알고리즘이란?
라인 스위핑(Line Sweeping) 알고리즘은 2차원 평면에서 선(line)을 한 방향으로 이동시키면서 특정 이벤트를 처리하는 알고리즘 기법이다.
주로 구간 문제, 교차 문제, 최근접 점 문제 등을 해결할 때 사용된다.

작동 방식:

이벤트 포인트 설정: 문제와 관련된 주요 이벤트(점, 선의 시작/끝 등)를 정렬된 리스트로 저장한다.

이벤트 처리: 정렬된 이벤트를 순차적으로 처리하며, 필요한 정보를 갱신하거나 결과를 도출한다.

활성 상태 관리: 현재 영향을 미치는 요소들을 자료구조(예: std::set)로 관리한다.

예제: 직사각형의 면적 구하기
주어진 직사각형들의 총 합집합 면적을 계산하는 문제를 라인 스위핑으로 해결해보자.

알고리즘 설명
x좌표를 기준으로 이벤트를 정렬 (사각형의 왼쪽 변(열림)과 오른쪽 변(닫힘))

스위핑하면서 y좌표 구간을 관리 (std::set 또는 std::map 활용)

면적을 구할 때는 현재 유효한 y구간의 길이를 계산하여 반영

C++ 코드 예시

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

struct Event {
    int x, y1, y2, type; // x좌표, y구간 (y1~y2), type (1: 열림, -1: 닫힘)
    bool operator<(const Event& e) const {
        return x < e.x;
    }
};

struct Segment {
    int y1, y2, count;
    bool operator<(const Segment& s) const {
        return y1 < s.y1;
    }
};

vector<Event> events;
multiset<Segment> activeSegments;

int compute_union_area(vector<Event>& events) {
    sort(events.begin(), events.end()); // x 좌표 기준 정렬

    int prev_x = events[0].x;
    int total_area = 0;

    for (const auto& e : events) {
        int dx = e.x - prev_x;
        
        // 현재 활성화된 y 구간의 길이 합 계산
        int total_y_length = 0;
        int last_y = -1;
        int open_count = 0;

        for (const auto& seg : activeSegments) {
            if (open_count > 0) {
                total_y_length += seg.y1 - last_y;
            }
            open_count += seg.count;
            last_y = seg.y1;
        }

        total_area += dx * total_y_length; // 직사각형 면적 증가
        prev_x = e.x;

        // 현재 이벤트 적용
        if (e.type == 1) { // 열림
            activeSegments.insert({e.y1, 1});
            activeSegments.insert({e.y2, -1});
        } else { // 닫힘
            activeSegments.erase(activeSegments.find({e.y1, 1}));
            activeSegments.erase(activeSegments.find({e.y2, -1}));
        }
    }

    return total_area;
}

int main() {
    int n;
    cout << "사각형 개수 입력: ";
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        events.push_back({x1, y1, y2, 1});  // 시작점 (열림)
        events.push_back({x2, y1, y2, -1}); // 끝점 (닫힘)
    }

    int total_area = compute_union_area(events);
    cout << "총 합집합 면적: " << total_area << endl;

    return 0;
}