[이론] 스위핑 알고리즘

 🤔 스위핑 알고리즘이란?

 : '빗자루로 쓸기' 기법. 특정 방향으로 가상의 선을 옮겨가며 마주치는 사건을 순서대로 처리하는 방식.

 

스위핑 알고리즘을 사용하는 가장 큰 이유는 효율성이다. 2차원 평면의 문제를 1차원적인 순서 문제로 변환하기 때문에 전체 데이터를 다 확인해보지 않아도 정답을 찾아낼 수 있기 때문이다.

보통 정렬에 $O(N log N)$이 걸리고, 각 사건을 처리할 때 트리 구조 등을 사용하면  $O(N log N)$이 걸리므로 전체 시간 복잡도를 확 낮출 수 있다.

---

 🛠️ 동작 원리

1. 정렬 (Sorting): 모든 요소를 처리할 방향에 맞춰 정렬한다. ex) x 좌표 순, y 좌표 순 ...

2. 처리 (Processing): 정렬된 순서대로 요소를 확인하며 현재 위치에서의 상태를 업데이트하고 정답을 구한다.

 

스위핑 알고리즘은 주로 기하 문제에서 사용되는 편이다.

• 선분 교차: 평면 위 선분 중 교차하는 쌍 찾기.
• 사각형의 합집합 넓이: 여러 개의 직사각형이 겹쳐 있을 때 전체 면적 구하기.
• 가장 가까운 두 점 찾기: 평면 위 수많은 점 중 거리가 가장 짧은 두 점 찾기.
• 일정 관리: 회의실 배정이나 겹치는 시간대 최대 인원 구하기.

 💡 예시: 선분 교차

여러 선분의 교차점을 찾는 문제를 예로 들어보자. 모든 선분 쌍을 하나하나 비교하면 $O(N^2)$만큼의 시간 복잡도가 필요하다. 대신 스위핑을 사용하면 시간 복잡도를 $O(N log N)$까지 줄일 수 있다.

• 가상의 수직선을 왼쪽에서 오른쪽으로 이동시킨다.
• 선분의 왼쪽 끝점을 만나면 현재 선분 목록에 추가한다.
• 선분의 오른쪽 끝점을 만나면 목록에서 삭제한다.

스위핑 방식을 사용하면, 선분을 목록에 삽입하거나 삭제할 때 인접한 선분과의 교차 여부만 확인하면 된다.

---

✍🏻 관련 문제

 ❓ 문제

백준 2170번: 선 긋기 https://www.acmicpc.net/problem/2170

백준 1911번: 흙길 보수하기 https://www.acmicpc.net/problem/1911

백준 11000번: 강의실 배정 https://www.acmicpc.net/problem/11000

 

 💡문제풀이

[BOJ Java] 백준 2170번: 선 긋기