스위핑 (Sweeping)

정의

스위핑 (Sweeping) 은 시간 또는 공간 축 위의 이벤트를 정렬한 뒤, 한 방향으로 훑으며 상태를 갱신해 문제를 푸는 기법입니다. 선분 교차, 구간 합집합, 최대 겹침 수 등 기하 / 구간 문제에서 O(N log N) 정렬 + O(N) 스윕으로 naive O(N²) 를 피할 수 있습니다.

문제 상황과 동기

선분 N 개가 주어지고 “최대 몇 개가 겹치는가?”를 물을 때,

• naive: 모든 점을 샘플링하거나 N² 페어 비교. 연속 좌표라면 불가능.
• sweeping: 각 선분의 시작 / 끝을 이벤트로 만들어 정렬, 수평선(또는 시간선)을 왼쪽에서 오른쪽으로 밀면서 현재 활성 선분 수를 추적. 총 O(N log N).

핵심 통찰: 이벤트를 정렬하면, 상태 변화는 순서대로 한 번씩만 처리. 계산 기하 / 구간 스케줄링에서 가장 많이 쓰이는 패턴 중 하나입니다.

시각화

핵심 아이디어

invariant: 스윕 라인이 현재 위치 x 를 지날 때, 활성 상태인 객체들만 관리. 이벤트 발생 순서대로 처리하므로, 모든 객체를 동시에 들고 있을 필요가 없습니다.

events = []
for each segment [l, r]:
    events.append((l, +1))   # start
    events.append((r, -1))   # end
events.sort()

active = 0
max_active = 0
for x, delta in events:
    active += delta
    max_active = max(max_active, active)

확장:

• 선분 교차 검사: Bentley-Ottmann 알고리즘. 수평선을 위에서 아래로 내리며 교차점 이벤트 추가.
• 구간 합집합 길이: 정렬 후 병합. max(prev_end, curr_start) 비교.
• 직사각형 면적 합: 수직 이벤트 + 세그먼트 트리.
• Voronoi 다이어그램: Fortune’s algorithm 도 스위핑 기반.

알고리즘

최대 겹침 수 (Max Overlapping Intervals)

max_overlap(intervals):
    events = []
    for [l, r] in intervals:
        events.append((l, START))
        events.append((r, END))
    events.sort()

    active = 0, max_active = 0
    for (x, type) in events:
        if type == START:
            active++
        else:
            active--
        max_active = max(max_active, active)
    return max_active

구간 합집합 길이

union_length(intervals):
    events = sorted(intervals, key=lambda x: x[0])
    total = 0
    prev_end = -∞
    for (l, r) in events:
        if l > prev_end:
            total += (r - l)
            prev_end = r
        else:
            if r > prev_end:
                total += (r - prev_end)
                prev_end = r
    return total

구현

// N 개 구간 [l, r], 최대 몇 개가 동시에 활성?
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  vector<pair<int, int>> ev;
  for (int i = 0; i < n; i++) {
      int l, r; cin >> l >> r;
      ev.push_back({l, +1});
      ev.push_back({r, -1});
  }
  sort(ev.begin(), ev.end());
  int active = 0, mx = 0;
  for (auto [x, d] : ev) {
      active += d;
      mx = max(mx, active);
  }
  cout << mx << "\n";
}

# N 구간, 최대 겹침 수
import sys
input = sys.stdin.readline
​
n = int(input())
ev = []
for _ in range(n):
  l, r = map(int, input().split())
  ev.append((l, +1))
  ev.append((r, -1))
ev.sort()
active, mx = 0, 0
for x, d in ev:
  active += d
  mx = max(mx, active)
print(mx)

// N 구간, 최대 겹침 수
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      List<int[]> ev = new ArrayList<>();
      for (int i = 0; i < n; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int l = Integer.parseInt(st.nextToken());
          int r = Integer.parseInt(st.nextToken());
          ev.add(new int[]{l, +1});
          ev.add(new int[]{r, -1});
      }
      ev.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
      int active = 0, mx = 0;
      for (int[] e : ev) {
          active += e[1];
          mx = Math.max(mx, active);
      }
      System.out.println(mx);
  }
}

4
1 4
2 5
3 6
7 8

3

3
1 10
2 9
3 8

3

구간 합집합 예제

// N 개 구간 [l, r] 의 합집합 길이
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  vector<pair<int, int>> a(n);
  for (auto& [l, r] : a) cin >> l >> r;
  sort(a.begin(), a.end());
  int total = 0, prev = -1e9;
  for (auto [l, r] : a) {
      if (l > prev) {
          total += r - l;
          prev = r;
      } else if (r > prev) {
          total += r - prev;
          prev = r;
      }
  }
  cout << total << "\n";
}

# N 구간 합집합 길이
import sys
input = sys.stdin.readline
​
n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
a.sort()
total, prev = 0, -10**9
for l, r in a:
  if l > prev:
      total += r - l
      prev = r
  elif r > prev:
      total += r - prev
      prev = r
print(total)

3
1 4
3 7
10 12

9

복잡도

정렬이 병목. 이벤트 수가 2N (시작 + 끝) 이므로 상수가 약 2배.

변형 / 활용

함정

1. 이벤트 순서 (시작 vs 끝)

같은 좌표에서 시작 이벤트가 끝 이벤트보다 먼저 와야 하는지 나중에 와야 하는지가 문제마다 다릅니다. 예: “구간 [l, r] 이 닫힌 구간이냐 열린 구간이냐?” 에 따라 active++ 와 active— 순서가 바뀝니다.

// 닫힌 구간: 같은 x 일 때 시작을 먼저
events.push_back({l, 0, +1});   // 0 = start
events.push_back({r, 1, -1});   // 1 = end
sort(events.begin(), events.end());

2. 좌표 압축 (Coordinate Compression)

좌표 범위가 10^9 이상이면 직접 배열 인덱스로 쓸 수 없습니다. 이벤트 좌표만 모아 압축한 뒤, 맵 / 정렬된 벡터로 접근합니다.

3. 실수 좌표

기하 문제에서 교차점이 실수일 때, 부동소수점 오차로 정렬 순서가 불안정할 수 있습니다. 정수 / 분수 연산 또는 epsilon 비교가 필요합니다.

4. 다차원 스윕

2D 는 수직 / 수평 두 축을 모두 스윕하거나, 한 축을 스윕하며 다른 축을 세그먼트 트리로 관리합니다. 구현이 복잡하므로 1D 로 환원 가능한지 먼저 확인합니다.

BOJ 연습 문제

참고

• 누적 합 (1D 정적 쿼리)
• 세그먼트 트리 (2D 스윕 + 구간 쿼리)
• 두 포인터 (정렬 후 양 끝에서 좁히기)