ACM 105, The Skyline Problem

※ 파란에서 이전하면서 코드가 없어졌다... 이런. 다시 짜야할 듯 허...

주어진 건물의 외곽선만을 얻는 문제이다. 따라서 선분(left == right 인 입력. 폭이 0이므로 보이지 않는다)은 무시해도 된다. 출력 형태는 생소할 수 있는데, 상향 벡터와 하향 벡터를 이용한다.

 

경계값 때문에 수 시간을 고생한 것이 아주아주 기억에 남는다... 여기 사용한 알고리즘은 글보다 그림으로 설명하는 편이 낫다.

 

세 개의 건물 값을 입력받았다고 가정하자. 먼저 prevHighestBuilding(건물의 폭과 높이를 멤버 변수로 가진다)을 잡아야 한다. 이 변수의 값을 폭은 10000(문제에서 지정한 최대값), 높이는 0으로 둔다.

 

이제 0부터 시작해서 10000까지 x축을 탐색한다. 그러는 중에 점을 발견하면 루틴을 수행한다.

 

건물을 발견했다. 이전 건물보다 높으므로 prevHighestBuilding를 이 건물 값으로 설정한다. 상향 벡터 값(탐색 위치, 가장 높은 건물 높이)을 출력한다. 다시 탐색을 계속한다.

 

 

 

건물을 발견했다. prevHighestBuilding보다 낮다. 그러나 이 건물의 폭이 길어서  prevHighestBuilding으로도 가려지지 않는다. 따라서 이 건물의 처리를 미루기 위해 겹쳐지는 시작 위치를 안 겹쳐지는 위치로 옮긴다.

 

 

 

 

 

 

 

 

 

 

그러면 이런 형태가 된다. 즉 처리 가능할때까지 계속 연기하는 전략을 사용했다. 다시 탐색을 시작한다.

 

 

 

 

 

 

 

 

prevHighestBuilding 보다 높은 건물을 발견했다. 위에서 파란 건물을 처리했던 것처럼, prevHighestBuilding 의 값을 더 높은 건물의 것으로 바꾼다. 상향 벡터를 표시하고 다시 탐색한다.

 

 

 

 

 

 

 

 

 

prevHighestBuilding 보다 낮은 건물을 발견했다. 이전에 빨간 건물을 처리했을 때와 같다. 즉, 빨간 건물의 폭이 prevHighestBuilding 로 가려지지 않으므로, 또 다시 처리를 미룬다.

 

 

 

 

 

 

 

 

 

그럼 이렇게 된다. 또 탐색한다.

 

 

 

 

 

 

 

 

 

탐색 위치와 현재 위치에서 가장 높은 건물의 끝 위치가 같다. prevHighestBuilding 에는 두번째 높은 건물의 값을 넣는다. 이제 하향 벡터(탐색 위치, 두번째로 높은 건물 높이) 를 출력한다. 또 탐색한다.

 

 

 

 

 

 

 

 

 

 

탐색 위치와 현재 위치에서 가장 높은 건물의 끝 위치가 같다. 다시 하향 벡터를 출력한다. prevHighestBuilding의 높이는 0이 된다.

 

건물이 또 나올때까지 계속 탐색한다.