[알고리즘] Sweeping Algorithm : 라인 스위핑 알고리즘
Sweeping Algorithm
라인 스위핑 알고리즘은 무엇일까? 사실 개념 자체는 매우 단순하다.
공간이나 직선 상에서 한쪽 시작점을 기준으로 반대편 종료지점 까지 scan하면서 지나가는데, 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 판단기준이 되는 기준 을 적용해 주면 정답이 구해지는 형태입니다.
이처럼 알고리즘의 구조 자체는 간단합니다.
즉, 스위핑 알고리즘 문제들은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현하게 해야한다.
대표적인 문제로 백준의 선 긋기 문제가 있습니다.
2170번: 선 긋기
첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.
www.acmicpc.net
이 문제를 배열을 20억 칸이나 잡아서 해결하려 들면 풀수가 없습니다.
일단 input으로 주어진 선들을 pair로 저장하여 vector에 삽입해 줍니다.
1) 정렬
우선 각 선들의 시작좌표지점을 기준으로 정렬을 진행합니다.
sort(vec.begin(), vec.end());이를 그림으로 보면 다음과 같이 되어있습니다.
사진 설명을 입력하세요.
왼쪽 부분의 길이 4 + 오른쪽 부분 길이 1 을 구하면 총 길이는 5가 됩니다.
방금 구한 5라는 길이를 구하려면 어떻게 해야할까?
2) 순회
우선 초기값으로 하늘색 선을 생각하자.
시작지점 = 1, 종료지점 = 3 을 잡는다. 이는 vector안에 정렬된 값들중 첫번째 pair에 해당한다.
2번째 초록색 선을 생각해 보자.
초록색 선은 하늘색 선과 부분이 겹치기 때문에 종료지점을 늘려도 된다.
종료지점 = 5가 된다.
3번째 빨간색 선을 생각해 보자.
빨간선 또한 초록선과 일치하는 부분이 있기에 종료지점을 늘려주면 된다.
종료지점 = 5가 된다.
4번째 보라색 선을 생각해 보자.
이점은 이전의 선들과 겹치는 부분이 없다. 따라서 이전의 선의 길이(종료지점 - 시작지점) 을 결과값 변수에 더한후,
시작지점 = 6, 종료지점 = 7 로 각각을 보라색 선분의 좌표로 초기화 시킨다.
이 알고리즘의 형태는, 수평선의 왼쪽 끝에서부터 훑다가 마주치는 선분이 있으면 판단기준에 맞게 처리를 해 주는 방식이라 할 수 있습니다.
이렇게 순회를 마치고 나면 결과값을 얻을 수 있습니다.
이처럼 직선 말고도, 평면 이상에도 적용 가능한 알고리즘이다.