Plane Sweeping BOJ 3392 화성 지도 7626 직사각형

plane sweeping(평면 스위핑, line sweeping이라고도 함) 에 대해 공부해보려 한다.

일단 JM book에 나와있는 평면 스위핑은 O(N제곱)의 시간복잡도를 가진다. 이 것으로 3392 화성 지도 문제는 통과됐지만 아마 7626번 문제를 풀기위해선 좌표압축을 하고 O(NlogN)의 플레인 스위핑이 필요하다. 

O(NlogN)짜리 평면 스위핑을 위해서는 segment tree를 써야하는데 감사하게도 검색해보면 잘 정리된 블로그가 몇 개 있다.

 그 중 내가 참고한 블로그인데

http://blog.naver.com/PostView.nhn?blogId=choyi0521&logNo=220020192420

그림과 함께 매우 잘 설명이 되어있다. 하지만 아마 O(N제곱)짜리 plane sweeping도 이해 못한 상태에서 본다면 전혀 이해가 안될 수도 있다...(내가 그랬다.) 그리고 위의 블로그에는 좌표 압축을 하는 경우와 하지 않는 경우 둘 다 코드가 있다.

일단 난 좌표압축이 필요한 경우를 공부해 보려고 한다.

JM book 의 O(N제곱) plane sweeping 이해 -> 세그먼트 트리, 좌표 압축에 대해 공부 -> O(NlogN)짜리 plane sweeping 공부 

일단 위의 블로그에서 설명하는 plane sweeping알고리즘의 원리 자체는 O(N제곱)짜리와 같지만 segment tree를 사용하는데, segment tree가 일반적인(내가 여태 사용해 왔던) segment tree와 좀 다르다.

라인 하나로 왼쪽에서부터 오른쪽으로 평면을 쓸면서 봐야하는데 보면서 만나는 직사각형의 세로 선들을 구별해서(직사각형의 왼쪽 세로선인지 오른쪽 세로선인지..) count를 해줘야 한다. 그리고 이 세그먼트 트리에서는 count에 따라 상위 노드를 업데이트 할지 말지 결정하게 된다.

좌표 압축을 한 상태에서 봐도 세그먼트 트리는 y축의 모든 구간을 다 커버한다. 즉 라인이 움직이면서 만난 직사각형의 y축 범위가 어느 범위든 간에 다 커버된다. 그리고 세그먼트 트리를 이용하면 세그먼트 트리에서 y축 범위에 해당하는 부분을 logN만에 업데이트하는데, 원래 세그먼트 트리에서 range update는 lazy propagation을 쓰지 않으면 range * logN만큼 걸렸다. 

그래서 어찌보면 여기서 사용하는 segment tree의 방식이 lazy propgation과 형태가 조금 비슷..?..하다고 볼 수 있겠다.

어쨌든, update를 할 때, 해당 범위의 leaf node들까지 다 업데이트 하는 것이 아니라 해당 범위에 해당하는 가장 위쪽의 node들만 업데이트 한다. 그리고 직사각형의 시작 부분에 해당하면 +1, 끝부분에 해당하는 세로 선이면 -1을 해서 count를 기록한다.

이 세그먼트 트리의 노드들은 count값과 y축의 크기값을 가지고 있는데, count가 1이상인 것은 현재 라인이 y축의 크기만큼 직사각형과 겹쳐있다는 뜻이고 count는 겹쳐있는 직사각형의 개수를 뜻한다. 

count가 1이상이면 해당 범위에 해당하는 가장 위쪽의 node에 해당하는 것으로 보면되고, y축의 크기값은 존재하는데 count 가 0이면 count가 1이상인 노드들의 합을 저장하고 있는 것으로 보면된다. 그리고 우리가 필요로 하는 것은 현재 라인이 직사각형들과 겹쳐 있는 총 길이이고 그 값은 전 범위를 나타내는 세그먼트 트리의 루트 노드에 저장되어 있다.

바로 그 루트 노드값이 logN만에 업데이트 될 수 있도록 segment tree를 사용하는 것이다.

그래서 좀 자세한 동작 과정을 보면 어떤 노드의 count값이 0에 해당하면 자식 노드들의 합으로 업데이트를 해준다. 하지만 count가 1이상이면 자식 노드들의 합으로 업데이트 하지 않고 자신의 값을 가지고 있는다. 즉, count값이 1이상인 것은 해당 범위에 직사각형이 존재한다는 것을 의미하고, 그 직사각형의 세로길이(y축 크기)를 기록해야 한다. 예를 들어, 그 노드의 자식 노드에 해당하는 부분에 있던 직사각형이 없어진 것을 반영해서 그 노드를 업데이트 해버리면, 그 노드에 해당하는 직사각형은 존재하는데, 그 직사각형의 일부가 사라지게 되는 잘못된 결과를 내게 된다.

라인을 움직이면서 어떤 직사각형의 시작 선이나 끝 선을 만날 때마다 변화가 생기므로 그 때마다 변화가 생기기전의 넓이 값을 계산해서 더해주는 식으로 나가는 것이다.

사실 내가 완벽히 이해하진 못했는데, 계속 고민하기 보다 일단 내가 이해한 데까지만 기록해두고 직접 짜보는 것이 좋을 것 같다. dfs, bfs가 그랬던 것처럼 dp가 그랬던 것처럼... 언젠가는 더 이해하게 될 날이 올 것이다. 너무 시간 끌지말고 앞으로 나아가자.

참고 : http://blog.naver.com/PostView.nhn?blogId=choyi0521&logNo=220020192420