212. Sweeping

이번에는 스위핑(Sweeping)에 대해서 살펴보자. 스위핑은 말 그대로 어떤 대상을 한쪽부터 차례대로 쓸면서 무언가를 확인한다는 것인데, 그 대상은 보통 $1$차원 직선, $2$차원 평면이다. 직선에서의 스위핑은 적당히 두 점을 잡아서 한쪽 점에서 다른쪽 점 방향으로 진행하는 것이 일반적이고, 평면에서의 스위핑은 한쪽 축을 기준으로 진행하거나 한 점을 중심으로 각도에 따라서 진행하는 것이 일반적이다. 그밖에 다른 구조에서 스위핑을 하는 경우도 존재할 수는 있지만 거의 나오지 않는다.

 

그러면 가장 간단한 형태인 $1$차원 스위핑을 예시로 살펴보자. 참고로 $1$차원 스위핑은 라인 스위핑(Line Sweeping), $2$차원 스위핑은 플레인 스위핑(Plane Sweeping)이라고 부르기도 한다.

 

이렇게 $6$개의 선분이 수직선상에 있을 때, 각각의 좌표를 포함하는 선분의 개수를 센다. (실제로는 하나의 수직선에 합쳐져서 표현해야 하지만, 그렇게 하면 겹쳐서 구별이 잘 안 되기 때문에 편의상 저렇게 나타내었다.)

 

가장 왼쪽 끝에서 스위핑을 시작한다. 선분의 시작점을 만났을 경우 좌표를 포함하는 선분의 개수에 $1$을 더한다. (선분의 끝점을 만났을 경우 $1$을 빼면 된다.)

계속해서 수직선을 따라가다가 선분의 시작점이나 끝점을 만날 때마다 좌표를 포함하는 선분의 개수를 갱신한다.

이런 식으로 계속해서 스위핑을 하다가 모든 구간이 다 끝나면 스위핑을 종료하면 된다. 스위핑을 종료했을 때 계산되는 값들은 다음과 같다.

이 그림에서는 선분의 시작점과 끝점이 전부 다 달랐지만, 선분의 시작점끼리, 끝점끼리, 또는 한 선분의 끝점과 다른 선분의 시작점이 겹치는 경우도 생길 수 있고 그럴 때 처리에 약간 신경을 써야 한다. 또한 구현을 할 때 선분이 끝점을 포함하는지 포함하지 않는지도 주의해야 한다.

 

[연습문제] (각도 스위핑 문제 추천받습니다)

 

BOJ 2170. 선 긋기 (Gold V)

라인 스위핑 기본 문제이다. 본문에서 설명한 대로 선을 시작점 기준으로 정렬한 다음 구간의 합집합을 구해 준다. 구현은 다음 글에서 소개할 IMOS법을 이용해서 하면 편하다.

 

BOJ 17619. 개구리 점프 (Gold III)

이것도 라인 스위핑인데 $y$좌표는 필요 없는 정보라서 무시해도 되고, $x$좌표가 겹치는 구간들을  분리 집합 등으로 구해 놓으면 된다.

 

BOJ 2672. 여러 직사각형의 전체 면적 구하기 (Gold II)

플레인 스위핑 기본 문제이다. $1$차원에서의 스위핑을 $2$차원으로 확장하면 된다.

 

BOJ 11012. Egg (Platinum II)

가장 쉬운 풀이가 뭐냐는 논란은 많지만 어쨌든 세그먼트 트리를 이용한 스위핑으로 풀 수 있다. 평면 스위핑을 세그먼트 트리로 최적화하는 것이다. 세그먼트 트리를 안 쓰는 풀이로 좌표 압축과 누적합을 쓰고 short 자료형으로 메모리를 줄이는 게 있다는데 그 풀이도 그렇게 낮은 티어는 아닌 것 같다. (골드 구간은 int 대신 short를 써야 통과한다는 이유로 몇 티어가 올라가는 걸 정당화할 수 있는 구간이다.)

 

→ solved.ac tag: sweeping