스위핑 기법(Sweeping Algorithm)

스위핑 기법(Sweeping Algorithm)

 

스위핑이란 어떤 선이나 공간을 한쪽에서부터 싹 쓸어버린다는 의미이며

스위핑 기법이란 한번만 전체 공간을 스캔하면서 마주치는 요소들에 뭔가를 해주면 정답이 구해지는 형태이다.

 

개념 자체는 굉장히 간단하지만 기본적으로 다른 기법이나 자료구조와 얽혀서 사용되므로 어려워진다.

즉 스위핑 기법이란 특정 알고리즘이라기보다는 방법론이라고 보면 될 듯하다.

 

 

 

사용 예시

 

예제 1) 1차원 공간에서의 스위핑

https://www.acmicpc.net/problem/2170

2170번: 선 긋기

수평선 위에 선분을 여러 번 긋고 모든 선분을 그은 후 수평선 위에 덮인 구간 길이 총합을 구하라는 문제

 

좌표가 -10억 ~ 10억으로 20억 1개 구간이고 선을 긋는 횟수 N이 최대 100만이다.

메모리제한은 192MB이므로 사용 가능 공간은 대략 192,000,000로 1.9억정도

반면 20억 1개의 int는 80억 4바이트 이므로 20억 1개 칸 배열을 만들고 사용하는 것은 불가능하다.

 

예제에 주어진 입력인 (1, 3), (2, 5), (3, 5), (6, 7)을 그림으로 나타내면 아래와 같다.

위처럼 답은 길이가 4인 구간과 1인 구간이 합쳐져 5가 되는데 지금은 구간이 1 ~ 7이라 한눈에 들어오고 쉽지만 20억개의 구간에 엄청 긴 선이나 여러개의 구간으로 나뉘어있다면 굉장히 복잡해 보일것이다.

 

이걸 쉽게 처리하려면 제일 왼쪽에서 시작하는 선분부터 오른쪽으로 차례대로 순회하면서 선이 겹치거나 이어지는지 확인해나가면 된다.

겹쳐지거나 이어진다면 합쳐서 하나의 선으로 취급하고

겹쳐지거나 이어지지 않고 따로 분리된 선이라면 이전 선의 길이를 결과값에 저장하고, 새로운 선에서 또 시작해서 겹쳐지거나 이어지는 선이 있는지 확인한다.

 

즉, 입력된 좌표 (x, y)가 있을때 좌표들의 x값을 기준으로 정렬한 후 오름차순으로 스위핑하는 것

 

정렬을 완료했다면 가장 왼쪽의 좌표부터 시작해서 이어지거나 겹치는지 확인해나간다.

먼저 첫 번째 선분은 자기 자신의 구간인 (1, 3)이 된다.

 

두 번째 선분인 (2, 5)는 첫번째 선분과 겹쳐진다.

즉 두 선을 합쳐서 (1, 5)로 취급하면 된다.

코드상에서는 아래와 같은 모양새가 된다.

if(line2.start <= line1.end) now_end = max(now_end, line2.end);

 

세 번째 선분인 (3, 5)는 이미 현재 구간에 포함되므로 변화가 없다. 다만 코드 상에선 max의 인자로 들어간 두 값이 같으니 변화가 없어보일 뿐이다.

 

네 번째 선분인 (6, 7)의 경우 기존의 선분과 겹치거나 이어지지 않는다.

그러므로 이전의 선분(1, 5)의 길이인 4를 result에 더하고, 구간을 새롭게 (6, 7)로 초기화한다.

 

※ 주의점

모든 선분을 다 순회하고 나면 마지막에 남은 구간인 (6, 7)의 길이 1도 빠트리지 말고 더해줘야 한다.

 

이로써 결과는 4 + 1 = 5로 5가 된다.

 

이처럼 수평선의 왼쪽부터 오른쪽으로 쓸어나가면서 마주치는 요소에 무언가 처리를 해주는 기법을 스위핑이라고 한다.

 

※ 정답코드

#include <iostream>
#include <vector>
#include <algorithm>

void fast()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
}

int main()
{
	fast();

	int N;
	std::cin >> N;

	// 선분이 몇개 입력될지 모르니 vector로
	// 입력된 좌표 x, y를 pair로 관리
	std::vector<std::pair<int, int>> lines;
	int x, y;
	while (N--) {
		std::cin >> x >> y;
		lines.push_back(std::pair(x, y));
	}

	// 좌표 (x, y)들을 x좌표순으로 오름차순정렬
	sort(lines.begin(), lines.end(), 
		[](std::pair<int, int> a, std::pair<int, int> b) { return a.first < b.first; }
	);

	int now_start = lines[0].first;
	int now_end = lines[0].second;
	int result = 0;
	for (int i = 1; i < lines.size(); i++) {		
		if (lines[i].first <= now_end) {
			now_end = std::max(now_end, lines[i].second);
		}
		else {
			result += (now_end - now_start);
			now_start = lines[i].first;
			now_end = lines[i].second;
		}			
	}
	result += (now_end - now_start); // 마지막 선분의 길이도 빼먹지 않고 더해주기

	std::cout << result;

	return 0;
}

 

 

많은 경우가 좌표나 도형같은것을 일정 기준에 맞게 정렬한 후 순서대로 훑는다는 공통점이 있다.

 

 

 

 

 

 

※ 참고문헌

https://blog.naver.com/kks227/220907708368