1. 알고리즘 배경과 개념
역사적 배경
스위핑 라인(Sweep Line) 알고리즘은 1976년 Michael Ian Shamos와 Dan Hoey가 "Geometric Intersection Problems" 논문에서 평면의 선분 교차 문제에 적용한 것이 시초입니다. 이들은 스캔라인 접근법과 효율적인 자료구조(자가균형 이진탐색트리)를 결합하여 N개의 선분 중 교차하는 쌍이 있는지를 O(N log N) 시간에 검출할 수 있음을 보였습니다.
이후 Bentley-Ottmann 알고리즘(1979년, Jon Bentley와 Thomas Ottmann이 개발한 모든 K개 교점을 O((N+K) log N) 시간에 찾는 알고리즘)과 Fortune의 알고리즘(1986년, Steven Fortune이 개발한 Voronoi 다이어그램을 O(n log n) 시간에 구성하는 알고리즘) 등으로 확장되어 현재 계산 기하학의 중요한 기법 중 하나가 되었습니다.
핵심 개념
스위핑 라인은 가상의 선을 한 방향으로 연속적으로 이동시키며 기하학적 문제를 해결하는 알고리즘 패러다임입니다. 주로 수직선을 왼쪽에서 오른쪽으로 이동시키며, 중요한 지점에서만 멈춰 계산을 수행합니다.
기본 원리
- 차원 축소: 2차원 문제를 1차원으로 변환
- 이벤트 기반: 상태 변화가 일어나는 지점에서만 계산
- 점진적 구성: 스위핑 진행에 따라 해답을 점진적으로 구성
주요 활용 분야
- 계산 기하학: 선분 교차, 볼록 껍질, Voronoi 다이어그램
- 컴퓨터 그래픽스: 충돌 감지, 가시성 계산
- VLSI 설계: 배선 검증, 마스크 검사
- 지리 정보 시스템: 공간 분석, 경로 최적화
- 로보틱스: 경로 계획, 장애물 회피
2. 알고리즘 특징과 복잡도
시간복잡도 분석
기본 스위핑 라인 알고리즘의 시간복잡도는 다음과 같습니다:
- 최선/평균/최악: O(n log n)
- 정렬 단계에서 O(n log n)이 소요되고, 스위핑 과정에서는 총 O(n)개의 이벤트를 순차적으로 처리하므로 전체적으로 O(n log n)이 됩니다.
선분 교차 검출 같은 복잡한 경우:
- 최선: O(n log n) - 교차점이 없는 경우
- 평균: O(n log n + k) - k개의 교차점 존재
- 최악: O(n²) - 모든 선분 쌍이 서로 교차하는 경우 (k = O(n²))
주요 코딩테스트 활용 문제들
- 구간/선분 겹침 문제
- 최대 겹치는 구간 수 찾기
- 구간 합집합 넓이 계산
- 회의실 배정 문제의 변형
- 기하학적 문제
- 선분 교차 검출
- 가장 가까운 점 쌍 찾기
- 볼록 껍질 구성 (Graham Scan)
- 이벤트 기반 문제
- 건물 스카이라인 문제
- 철로/도로 건설 최적화
- 시간대별 활성 객체 관리
의사 코드
SWEEP_LINE_ALGORITHM(Objects)
1. events ← empty list
2. FOR each object IN Objects
3. CREATE start_event and end_event for object
4. ADD events to events list
5. END FOR
6.
7. SORT events by position (and type if same position)
8.
9. active_objects ← EMPTY_DATA_STRUCTURE
10. result ← empty list
11.
12. FOR each event IN events
13. current_position ← event.position
14.
15. IF event.type = START_EVENT THEN
16. INSERT event.object INTO active_objects
17. CHECK for interactions with neighboring objects
18. ELSE IF event.type = END_EVENT THEN
19. REMOVE event.object FROM active_objects
20. CHECK for new interactions between neighbors
21. // 교차 이벤트 고려 시: 객체들의 상대적 위치 역전 등 처리
22. END IF
23.
24. UPDATE result based on current state
25. END FOR
26.
27. RETURN result
참고: 대부분 스위핑 라인 문제(구간 오버랩, 철로 건설 등)에서는 시작과 끝 이벤트만 사용합니다. 교차점 이벤트는 선분 교차 검출과 같은 특수한 경우에만 필요하며, 이때는 스위핑 과정에서 동적으로 감지하여 이벤트 큐에 추가합니다.
3. 실제 구현 예시
예시 1: 구간 오버랩 최대 개수 찾기
문제: 1차원 선 위의 여러 구간들 중 가장 많이 겹치는 지점에서의 구간 개수를 구하기
import java.util.*;
class IntervalOverlap {
static class Event implements Comparable<Event> {
int position;
int type; // 1: 시작, -1: 끝
Event(int position, int type) {
this.position = position;
this.type = type;
}
@Override
public int compareTo(Event other) {
if (this.position != other.position) {
return Integer.compare(this.position, other.position);
}
// 같은 위치에서는 끝나는 이벤트를 먼저 처리
return Integer.compare(this.type, other.type);
}
}
public static int maxOverlappingIntervals(int[][] intervals) {
List<Event> events = new ArrayList<>();
// 이벤트 생성
for (int[] interval : intervals) {
events.add(new Event(interval[0], 1)); // 시작
events.add(new Event(interval[1], -1)); // 끝
}
// 이벤트 정렬
Collections.sort(events);
int maxOverlap = 0;
int currentOverlap = 0;
// 스위핑
for (Event event : events) {
currentOverlap += event.type;
maxOverlap = Math.max(maxOverlap, currentOverlap);
}
return maxOverlap;
}
}
예시 2: 철로 건설 문제(백준 13334번) - 차원 축소 예시
문제: 길이 d인 철로로 최대한 많은 사람의 집과 사무실을 모두 커버하기
차원 축소 과정:
- 2차원 정보: 평면상에서 (집, 사무실) 위치
- 1차원으로 축소: 각 사람을 [집] [사무실] 구간으로 변환
- 스위핑: 철로 끝점을 기준으로 1차원 선상에서 스위핑
import java.util.*;
class RailwayConstruction {
static class Event implements Comparable<Event> {
int railEndPosition; // 철로 끝점 위치
int change; // +1: 커버 시작, -1: 커버 종료
Event(int railEndPosition, int change) {
this.railEndPosition = railEndPosition;
this.change = change;
}
@Override
public int compareTo(Event other) {
if (this.railEndPosition != other.railEndPosition) {
return Integer.compare(this.railEndPosition, other.railEndPosition);
}
// 같은 위치에서는 종료(-1)를 먼저 처리
return Integer.compare(this.change, other.change);
}
}
public static int maxCoveredPeople(int[][] people, int railLength) {
PriorityQueue<Event> events = new PriorityQueue<>();
// 각 사람을 구간 [left, right]로 변환 (차원 축소!)
for (int[] person : people) {
int left = Math.min(person[0], person[1]);
int right = Math.max(person[0], person[1]);
// 철로로 커버 가능한 경우만 고려
if (right - left <= railLength) {
// 철로 끝점이 right에 있으면 이 사람 커버 시작
events.offer(new Event(right, 1));
// 철로 끝점이 left + railLength + 1에 있으면 커버 종료
events.offer(new Event(left + railLength + 1, -1));
}
}
int maxCount = 0;
int currentCount = 0;
// 스위핑 라인 실행
while (!events.isEmpty()) {
Event event = events.poll();
currentCount += event.change;
// 같은 위치의 모든 이벤트 처리
while (!events.isEmpty() &&
events.peek().railEndPosition == event.railEndPosition) {
currentCount += events.poll().change;
}
maxCount = Math.max(maxCount, currentCount);
}
return maxCount;
}
}
예시 3: 선분 교차 검출
문제: 평면상의 선분들 중 교차하는 선분 쌍이 있는지 검출
import java.util.*;
class LineSegmentIntersection {
static class Point {
double x, y;
Point(double x, double y) { this.x = x; this.y = y; }
}
static class Segment {
Point start, end;
int id;
Segment(Point start, Point end, int id) {
this.start = start;
this.end = end;
this.id = id;
}
// 스위핑 라인에서의 y 좌표 계산
double getY(double x) {
if (Math.abs(start.x - end.x) < 1e-9) return start.y;
return start.y + (end.y - start.y) * (x - start.x) / (end.x - start.x);
}
}
static class Event implements Comparable<Event> {
double x;
int type; // 0: 시작, 1: 끝
Segment segment;
Event(double x, int type, Segment segment) {
this.x = x;
this.type = type;
this.segment = segment;
}
@Override
public int compareTo(Event other) {
if (Math.abs(this.x - other.x) > 1e-9) {
return Double.compare(this.x, other.x);
}
return Integer.compare(this.type, other.type);
}
}
// 두 선분의 교차 여부 판단
static boolean doIntersect(Segment s1, Segment s2) {
// CCW(Counter-ClockWise) 알고리즘 사용
int d1 = ccw(s1.start, s1.end, s2.start);
int d2 = ccw(s1.start, s1.end, s2.end);
int d3 = ccw(s2.start, s2.end, s1.start);
int d4 = ccw(s2.start, s2.end, s1.end);
if (d1 * d2 < 0 && d3 * d4 < 0) return true;
// 한 직선 위에 있는 경우 처리
if (d1 == 0 && onSegment(s1, s2.start)) return true;
if (d2 == 0 && onSegment(s1, s2.end)) return true;
if (d3 == 0 && onSegment(s2, s1.start)) return true;
if (d4 == 0 && onSegment(s2, s1.end)) return true;
return false;
}
static int ccw(Point a, Point b, Point c) {
double cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
if (Math.abs(cross) < 1e-9) return 0; // 일직선
return cross > 0 ? 1 : -1; // 반시계방향 : 시계방향
}
static boolean onSegment(Segment seg, Point p) {
return Math.min(seg.start.x, seg.end.x) <= p.x &&
p.x <= Math.max(seg.start.x, seg.end.x) &&
Math.min(seg.start.y, seg.end.y) <= p.y &&
p.y <= Math.max(seg.start.y, seg.end.y);
}
public static boolean hasIntersection(Segment[] segments) {
List<Event> events = new ArrayList<>();
// 이벤트 생성
for (Segment seg : segments) {
double leftX = Math.min(seg.start.x, seg.end.x);
double rightX = Math.max(seg.start.x, seg.end.x);
events.add(new Event(leftX, 0, seg));
events.add(new Event(rightX, 1, seg));
}
Collections.sort(events);
// y 좌표 기준으로 정렬된 활성 선분들
TreeSet<Segment> activeSegments = new TreeSet<>((s1, s2) -> {
double y1 = s1.getY(events.get(0).x);
double y2 = s2.getY(events.get(0).x);
if (Math.abs(y1 - y2) < 1e-9) return Integer.compare(s1.id, s2.id);
return Double.compare(y1, y2);
});
// 스위핑 실행
for (Event event : events) {
if (event.type == 0) { // 선분 시작
// 인접한 선분들과 교차 검사
Segment lower = activeSegments.lower(event.segment);
Segment higher = activeSegments.higher(event.segment);
if (lower != null && doIntersect(lower, event.segment)) return true;
if (higher != null && doIntersect(higher, event.segment)) return true;
activeSegments.add(event.segment);
} else { // 선분 끝
Segment lower = activeSegments.lower(event.segment);
Segment higher = activeSegments.higher(event.segment);
// 제거 후 새로 인접하게 된 선분들 간 교차 검사
if (lower != null && higher != null && doIntersect(lower, higher)) {
return true;
}
activeSegments.remove(event.segment);
}
}
return false;
}
}
4. 구현시 주의사항
수치 안정성
- 부동소수점 연산에서 epsilon 값을 이용한 비교 (Math.abs(a - b) < 1e-9)
- 정수 좌표 사용 시 overflow 방지
경계 조건 처리
- 같은 위치에서 발생하는 여러 이벤트의 처리 순서
- 수직선과 평행한 선분들의 특별한 처리
자료구조 선택
- TreeSet/TreeMap (Java), set/map (C++): O(log n) 연산
- 우선순위 큐: 이벤트 관리
- 적절한 비교함수 정의
참고 자료
- Shamos & Hoey 원본 논문 (1976)
Michael Ian Shamos and Dan Hoey. "Geometric Intersection Problems." 17th Annual Symposium on Foundations of Computer Science (SFCS 1976), Houston, 25-27 October 1976, 208-215. - Wikipedia - Sweep Line Algorithm
https://en.wikipedia.org/wiki/Sweep_line_algorithm - Wikipedia - Bentley–Ottmann Algorithm
https://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm - Wikipedia - Fortune's Algorithm
https://en.wikipedia.org/wiki/Fortune's_algorithm - HackerEarth - Line Sweep Technique Tutorial
https://www.hackerearth.com/practice/math/geometry/line-sweep-technique/tutorial/ - USACO Guide - Sweep Line
https://usaco.guide/plat/sweep-line
'Algorithm' 카테고리의 다른 글
| [프로그래머스] 순위 (플로이드-워셜 Floyd-warshall) (0) | 2025.05.06 |
|---|---|
| [프로그래머스] 방의 개수 (그래프) (0) | 2025.05.05 |
| [프로그래머스] 네트워크 문제 (유니온 파인드 Disjoint Set) (0) | 2025.04.29 |
| [프로그래머스] 단어 변환 (BFS) (0) | 2025.04.28 |
| [프로그래머스] 징검다리 (이분탐색) (0) | 2025.04.28 |