스위핑 알고리즘이란?

스위핑(sweeping)은 '쓸다'라는 의미이다.
스위핑 알고리즘은 한 쪽에서 다른 쪽으로 스캔하가면서 쓸어가는 것이라고 보면 된다.

특별한 자료구조이나 구체적인 코드가 사용되는 것도 아니다.
그저 한 쪽에서 시작해서 다른 쪽으로 나아가며 차근차근 문제를 해결해 나가는 것이다.

스위핑 알고리즘 예시

BOJ 2170 - 선 긋기

선을 그엇을 때 총 길이를 구하는 문제다. 이때 겹치는 부분은 중복해서 세지 않는다.

이를 해결하는 방법은 아래와 같다.
1. 시작 순으로 정렬
2. 왼쪽 부터 차근히 오른쪽으로 스위핑

예시로 설명해보면,
1 3
2 5
3 5
6 7
위와 같이 정렬된다.

l = r = 0으로 세팅하고
1. 1 3 -> l=1, r=3
2. 2 5 -> l=1, r=5
3. 3 5 -> l=1 r =5
4. 6 7 -> ans += r-l(=5-1), l=6, r=7
5. ans += r-l(=7-6)
따라서 ans = 4 + 1 = 5 가 된다.

이런 식으로 겹치는 총 길이를 찾을 수 있다.

BOJ 2215 - 원형 네트워크

마찬가지로 스위핑 문제인데 이번엔 원형이다.

1. 시작점 s = 1~N 동안 반복한다.
   1. 시작점부터 시작하여 마찬가지로 왼쪽에서 오른쪽으로 스위핑해준다.
   2. 겹치는 길이를 구해주면 된다.

시작점에 따라서 각 pair를 연결할 때 시계와 반시계를 모두 시도해보게 된다.
pair = (u, v)라 할떄(u<v),
시작점이 u ~ v사이면 v->u방향으로 연결하고, 그렇지 않으면 u->v 방향으로 연결한다.

모든 s에 대해서 스위핑해주면 기본적으로 모든 연결을 시키게 되고 각 시작점 중 가장 최솟값을 가지는 경우가 결국 정답이 된다.