Skyline 해설

Skyline의 해설입니다.

개요

Skyline은 주어진 빌딩의 정보를 조합하여 최종적으로 만들어지는 공제선을 구해 출력하는 문제입니다.

개별적으로 입력되는 정보를 종합하여 만들어진 최종 결과를 출력해야 한다는 점에서 색종이(KOI 07’ 초등부 2번)와 유사한 문제라고 볼 수 있습니다.

건물이 가지는 정보는 시작점, 넓이 , 높이입니다. 문제에서 요구하는 것은 공제선의 구성 정보(가로, 세로 선분)이므로 결국 최종적으로 만들어지는 공제선이 어떻게 되어있는지를 건물의 정보를 이용하여 구해야 합니다.

따라서 ‘공제선을 어떻게 표현할 것인가?’가 문제 해결의 핵심이 되겠습니다.

먼저 공제선을 1,000,000 개 크기의 1차원 배열로 표현할 수 있겠습니다. 이러면 공제선을 읽는 시간은 느리겠지만 건물의 입력에 따른 공제선 정보 변경을 간단하게 처리할 수 있습니다. 원래 문제에서 요구하는 답안도 해당 형태입니다.

본 문제에서 별도의 메모리 제한이 없기 때문에 위 솔루션이 가능합니다만, 만약 메모리 제한이 있거나 가로의 범위가 INT_MAX와 같이 매우 큰 수라면 배열을 그대로 공제선으로 구현하기엔 제한이 생길 수 있습니다.

따라서 정석적인 풀이법은 공제선을 구성하는 각 점의 배열로 공제선을 표현하는 것입니다. priority_queue나 multiset과 같은 자료형을 사용하는 솔루션입니다.

이러한 풀이는 건물을 두 개의 요소 - 시작점 과 끝점 으로 분리하여 이용합니다. 공제선의 정보가 변하는 지점은 결국 건물이 시작하고 끝나는 지점들 뿐이기 때문입니다.

이후 해당 지점들을 끝점 우선, x좌표 오름차순, 동일 x좌표에 대해 y좌표 내림차순으로 정렬하여 공제선의 구성점을 찾아낼 수 있습니다. 이러한 기법을 스위핑 알고리즘이라고 합니다.

구현에 있어서 꽤 까다롭게 느껴질 수 있는 문제입니다. 다만 NESPA는 제한 조건이 널널하게 설정되어있기 때문에 배열을 이용한 풀이를 충분히 생각해볼 수 있어 고급 자료구조를 활용하지 않아도 100점을 무난히 받을 수 있는 문제라고 생각합니다.