스위핑 알고리즘은 좌표나 선분 등의 데이터를 정렬한 뒤, 왼쪽부터 오른쪽으로 한 번씩 스캔하면서 문제의 해답을 도출하는 기법입니다.
이 방법은 탐욕적 선택(그리디 알고리즘)의 성질을 활용하여, 각 시점에서 최적의 선택을 하며 전체 문제의 최적해를 구할 수 있습니다.
예시:
여러 선분이 주어졌을 때, 각 선분의 구간을 확인하며 겹치는 부분을 병합해, 전체 덮인 길이를 구하는 문제
1. 스위핑 알고리즘 개요
- 핵심 개념:
데이터를 정렬한 후 왼쪽부터 순차적으로 스캔하면서 “현재 구간”을 업데이트합니다.
- 특징:
- 탐욕적 선택: 매 순간 가장 왼쪽에 있는 선분(또는 현재 구간)을 기준으로 결정하며 진행
- 최적 부분 구조: 한 구간 내에서의 병합 결정은 독립적인 하위 문제로 취급할 수 있습니다.
2. 선분 병합 과정 이해하기
스위핑 알고리즘에서는 선분을 병합할 때 크게 두 가지 상황을 고려합니다.
2-1. 선분이 이어지는 경우 (Overlap)
- 상황 설명:
현재 구간에 저장된 선분과 새로 등장한 선분이 겹치거나 바로 인접할 때
→ 두 선분을 하나의 구간으로 병합합니다.
- 처리 방식:
- 갱신: 새 선분의 끝점을 현재 구간의 끝과 비교해, 더 큰 값으로 현재 구간의 끝을 업데이트합니다.
- 예시:
- 일반 겹침:
- 현재 구간: (1, 3)
- 새 선분: (2, 5)
→ 2 ≤ 3이므로 두 선분은 겹치며, 합쳐진 구간은 (1, 5)가 됩니다.
→ 새 선분 (2, 3)은 현재 구간 (1, 10) 내에 완전히 포함됩니다.
→ 갱신 시 max(10, 3) = 10이 되어 현재 구간은 그대로 (1, 10)으로 유지됩니다.
2-2. 선분이 끊어지는 경우 (Break)
- 상황 설명:
새 선분의 시작점이 현재 구간의 끝보다 크면, 두 선분은 겹치지 않습니다.
- 처리 방식:
1. 저장: 지금까지 병합된 구간의 길이를 결과에 누적합니다.
2. 새 구간 시작: 새 선분을 기준으로 새로운 구간을 설정합니다.
- 예시:
- 누적된 구간: (1, 5)
- 새 선분: (6, 7)
→ 6 > 5이므로, (1, 5) 구간의 길이 4를 결과에 저장한 후
→ 현재 구간을 (6, 7)로 재설정합니다.
3. 왜 시작점을 기준으로 정렬해야 할까?
3-1. 탐욕적 선택 보장
- 가장 왼쪽(시작점이 가장 작은) 선분은 문제 해답에 반드시 포함되어야 하는 기본 요소입니다.
- 이 선분을 기준으로 병합을 시작하면, 뒤따르는 선분과의 겹침 여부를 즉시 판단할 수 있습니다.
3-2. 최적 부분 구조 활용
- 정렬된 상태라면 한 번 병합한 구간은 독립적인 하위 문제로 취급할 수 있습니다.
- 새로운 선분 등장 시 현재 구간과만 비교하면 되므로, 누락 없이 전체 영역을 커버하며 최적해를 도출할 수 있습니다.
3-3. 정렬의 장점
- “가장 왼쪽”이라는 고정된 기준을 세우므로, 구간 사이의 간극이나 중복을 놓치지 않고,
모든 선분을 체계적으로 처리할 수 있습니다.
4. 선 긋기 (BOJ 2170) 문제
문제
>매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다.
선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.
이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오.
선이 여러 번 그려진 곳은 한 번씩만 계산한다.
입력
- 첫 줄: 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)
- 다음 N개의 줄: 각 선분의 시작점 x와 끝점 y
(단, -1,000,000,000 ≤ x < y ≤ 1,000,000,000)
출력
- 전체 선이 덮은 길이를 출력합니다.
(여러 번 그린 영역은 중복해서 계산하지 않습니다.)
예제
- 예제 입력:
4
1 3
2 5
3 5
6 7- 예제 출력:
5문제 해결 전략
- 정렬:
선분들을 시작점 기준으로 오름차순 정렬
→ 정렬 결과: (1, 3), (2, 5), (3, 5), (6, 7)
- 병합 과정:
→ 새로운 구간 (6, 7)로 재설정.
- 결과 계산:
최종 결과는 (5 – 1) + (7 – 6) = 4 + 1 = 5
시각적 자료
좌표: 1 2 3 4 5 6 7
|==== (1,5) ====| |== (6,7) ==|5. Java 코드 예제
아래는 위 전략을 구현한 Java 코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
class BOJ선_긋기 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<int[]> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
int[] ab = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
list.add(ab);
}
list.sort(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[0], o2[0]);
}
});
int result = 0;
int currentStart = 0;
int currentEnd = 0;
for (int[] ab : list) {
// 처음인 경우
if (currentStart == 0 && currentEnd == 0) {
currentStart = ab[0];
currentEnd = ab[1];
} else if (ab[0] >= currentStart && ab[0] <= currentEnd && ab[1] > currentEnd) {
// 포함되지는 않으면서 겹치는 경우
currentEnd = ab[1];
} else if (ab[0] > currentEnd) {
// 겹치지 않는 경우
result += Math.abs(currentEnd - currentStart);
currentStart = ab[0];
currentEnd = ab[1];
}
}
// 마지막 누적
result += Math.abs(currentEnd - currentStart);
System.out.println(result);
}
}6. 마무리 및 요약
- 스위핑 알고리즘은 정렬과 한 번의 순회를 통해 선분 병합 문제를 효율적으로 해결하는 방법입니다.
- 핵심 포인트:
- 연결됨 (Overlap):
새 선분이 현재 구간과 겹치거나, 심지어 현재 구간 내에 완전히 포함되는 경우
→ 현재 구간의 끝 = max(현재 구간의 끝, 새 선분의 끝) 로 갱신
새 선분의 시작점이 현재 구간의 끝보다 크면
→ 지금까지 병합한 구간의 길이를 결과에 누적한 후,
새로운 구간으로 전환합니다.
시작점을 기준으로 정렬함으로써 항상 왼쪽부터 순차적으로 처리하게 되고,
이는 탐욕적 선택과 최적 부분 구조를 보장해 전체 문제의 최적해를 도출합니다.