스위핑 (Sweeping)

목차

개요

설명

일반화

코드

---

개요

스위핑 (Sweeping)은 "쓸다" 를 의미합니다. 스위핑 알고리즘 이란 말 그대로 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것이라고 보시면 됩니다.

 

이 알고리즘은 특정한 자료구조나 구체적인 코드가 있는 것은 아닙니다. 단지, 한쪽 방향에서 시작해서 다른 방향으로 차근차근 해결해 나가는 기법입니다.

 

이러한 특성 때문에, 보통 좌표와 관련있는 문제가 많이 보이는 듯 합니다.

---

boj 2170 - 선 긋기

이 문제는 일직선상에 여러 길이의 선을 그어, 최종적으로 마지막에 그려져 있는 선의 길이를 구하는 문제입니다. 이 선끼리는 겹칠 수 있기 때문에 그린 길이의 총 합보다 그려져 있는 길이가 작거나 같을 수 밖에 없습니다.

 

여기서, 그릴 수 있는 좌표의 범위는 -10억 ~ 10억입니다. 때문에 배열을 만들어 그려진 좌표를 표기한다라는 해법은 불가능합니다. 배열 길이만 20억 bit (대략 2.5억 byte)가 필요하기 때문이죠.

 

따라서 스위핑 (sweeping) 알고리즘을 적용해서 풀어야 합니다.

 

처음 접하면 어려울 수 있지만, 의외로 코드는 간단합니다. 인풋으로 들어오는 선분들을 시작점 기준으로 정렬하여 가장 왼쪽부터 차례로 보면 풀 수 있습니다.

 

이 때, 차례로 접하면서 접하는 case는 3가지 입니다. 1) 선분이 새로 시작되는 경우, 2) 선분이 겹치지만 일부는 안겹치는 경우 (선분 확장), 3) 선분이 기존에 그렸던 선분에 완전히 포함되는 경우

---

설명

boj 2170의 (약간 변형된) 예제를 사용해보겠습니다.

4
2 5
3 5
1 3
6 7

아래와 같은 수직선에서 위의 예제를 하나씩 사용해 볼까요?

먼저, 사용하기에 앞서서 입력들은 정렬되어 있어야 합니다. 우리는 왼쪽부터 오른쪽으로 차례로 sweep할 것이기 때문에, 시작점을 기준으로 정렬 해야합니다.

 

따라서 시작점을 기준으로 정렬하면 다음과 같은 (원래 백준의) 예제로 바뀌겠죠?

1 3
2 5
3 5
6 7

Step 1: 1 ~ 3 (새 출발)

이제 1 ~ 3을 적용해 봅시다. 여기서 현재 그리고 있는 연결된 선분의 가장 처음과 끝을 각각 start, end라고 하겠습니다.

1 ~ 3 을 그려보면 start 는 1, end 는 3이 되겠죠.

 

Step 2: 2 ~ 5 (선분 연장)

이제 2 ~ 5를 적용해 봅시다.

2 ~ 5 를 그려보면 start는 변함 없고, end 는 3에서 5로 바뀌었습니다.

 

Step 3: 3 ~ 5 (이미 그려진 선분 내에 포함)

이제 3 ~ 5 를 적용해 봅시다.

3 ~ 5를 그려보면, start는 변함 없고, end 도 변함이 없습니다.

 

Step 4: 6 ~ 7 (새 출발)

이제 마지막인 6 ~ 7 을 적용해 봅시다.

마지막 6 ~ 7 선분은 우리가 Step 1부터 3까지 그려온 선분과 전혀 겹치지 않습니다. 따라서 새롭게 그려야 합니다.

그 전에, 우리가 지금까지 그려온 선분의 길이를 위 그림처럼 정답에 증가시켜줘야 합니다. 이 값은 (End - Start)와 같습니다.

 

이제 6 ~ 7 은 Start는 1에서 6으로, End는 5에서 7로 바꿔주면 됩니다.

 

마찬가지로, 마지막 인풋이므로 더이상의 선분 확장은 없습니다. 따라서 이 선분의 길이도 정답에 포함 시켜줘야 합니다.

최종적으로 정답은 5가 됩니다.

 

---

일반화

위에서 살펴보면 과정이 크게 3가지로 구분됩니다.

우리가 처리할 현재의 인풋을 a ~ b라고 해보죠.

 

1. 완전히 새로운 선분 ( a > End )

Step 1과 Step 4가 해당합니다. Step 1에서 Start와 End가 같은 값의 -INTMAX로 초기화 되어있다면, 예외처리를 해줄 필요가 없습니다.

 

만약 지금까지의 end값보다 a가 크다면, a ~ b는 우리가 그려왔던 start ~ end범위에 속하지 않습니다.

이 때는 직전까지 그렸던 선분의 길이 (end - start) 값을 정답에 포함해주고

 

이제 start와 end를 각각 a와 b 값으로 초기화 시켜주면 됩니다.

 

2. 일부만 포함된 선분 (a <= End && b > End)

step 2가 이에 해당합니다. 이 때는 단순히 End값만 b로 갱신해주면 됩니다.

 

3. 완전히 포함된 선분 (b <= End)

step 3이 이에 해당합니다. 별도로 해줄 일이 없습니다.

---

코드

이 코드는 일직선에서 오른쪽으로 sweep하는 코드입니다. 구현에 따라 오른쪽에서 왼쪽으로 sweep하는 코드도 구현이 가능합니다.

 

※주의할 점

1. 문제에서 input은 정렬되어 있다는 언급이 없습니다. 따라서 배열로 한 번 다 받은 다음에 시작점을 기준으로 정렬해줘야 합니다.
2. 초기화를 잘 시켜줘야 합니다. start와 end값은 입력 범위 최솟값인 -1,000,000,000보다 작은 수이면 됩니다. 또한 start와 end의 초기값은 같은게 좋습니다. (별도의 예외처리를 필요로하지 않음)

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct vec{
        int a;
        int b;
}Vec;

//시작점 기준 정렬
bool cmp(const Vec& a, const Vec& b){
        return a.a < b.a;
}

Vec arr[1000000];
int N, Start, End, ans;
int main(){
        End = Start = -1000000001;
        scanf("%d",&N);
        for(int i=0;i<N;i++){
                scanf("%d %d",&arr[i].a, &arr[i].b);
        }
        //정렬 필요
        sort(arr,arr+N,cmp);

        for(int i=0;i<N;i++){
                if(End < arr[i].a){ //case 1 (새 선분): 현재 그린 선분의 길이 정산 후, Start와 End 갱신 (End 갱신은 case 2 if branch에서 처리)
                        ans += End - Start;
                        Start = arr[i].a;
                }
                if(End < arr[i].b) //case 2 (선분 확장): End 변수만 갱신
                        End = arr[i].b;
                        
                //case 3 (포함된 선분): 별도의 작업이 필요 없음
        }
        //마지막 선분 처리
        ans += End - Start;
        printf("%d\n",ans);
        return 0;
}