[알고리즘 이론] 9. 라인 스위핑

라인 스위핑

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

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

예시

• 라인을 1,3 / 2,5 / 3,5 / 6,7 총 4개를 준다고 가정한다.

1. 라인들을 pair로 저장하고 pair배열에 삽입 후 정렬
2. 처음 pair 의 시작점(1)을 start, 끝점(3)을 end 로 지정
3. 다음 pair인 2,5 에서 시작점인 2가 끝점보다 적으므로 패스, 끝점이 5로 3보다 크므로 끝점을 5로 바꿈
4. 다음 pair인 3,5 에서 시작점인 3이 끝점보다 작고, 5가 끝점이랑 같으므로 패스
5. 다음 pair인 6,7에서 시작점인 6이 끝점인 5 보다 크므로 이전 까지의 시작점 1과 끝점 5까지의 길이인 4를 결과에 더하고 시작점을 6으로 바꾸고, 끝점을 7로 바꾼다.
6. 다음 pair가 없으므로, 결과값인 5에 마지막 pair의 길이인 1를 더한 값(5)을 결과값에 넣고 반환.

알고리즘 문제 추천

1. 선 긋기 (골드 5)

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

2. 사냥꾼 (골드 3)

• https://www.acmicpc.net/problem/8982

참고 자료

https://sphong0417.tistory.com/37