[알고리즘] Sweeping Algorithm : 라인 스위핑 알고리즘

 

Sweeping Algorithm

라인 스위핑 알고리즘은 무엇일까? 사실 개념 자체는 매우 단순하다.

 

공간이나 직선 상에서 한쪽 시작점을 기준으로 반대편 종료지점 까지 scan하면서 지나가는데, 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 판단기준이 되는 기준 을 적용해 주면 정답이 구해지는 형태입니다.

이처럼 알고리즘의 구조 자체는 간단합니다.

 

즉, 스위핑 알고리즘 문제들은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현하게 해야한다.

 

대표적인 문제로 백준의 선 긋기 문제가 있습니다.

2170번: 선 긋기

이 문제를 배열을 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 로 각각을 보라색 선분의 좌표로 초기화 시킨다.

 

이 알고리즘의 형태는, 수평선의 왼쪽 끝에서부터 훑다가 마주치는 선분이 있으면 판단기준에 맞게 처리를 해 주는 방식이라 할 수 있습니다.

 

이렇게 순회를 마치고 나면 결과값을 얻을 수 있습니다.

 

이처럼 직선 말고도, 평면 이상에도 적용 가능한 알고리즘이다.