백준 14752번 Map Labeling ( Daejeon Nationalwide Internet Competition 2017 G번 )

문제

Map labeling is to place extra information, usually in the form of textual labels, next to features of interest within a map. The typical features depicted on a map are line features(e.g. roads, rivers, etc.), area features(countries, forests, lakes, etc.), and point features(villages, cities, etc.). In this problem, only the point features will be considered.

The basic requirements on the map labeling are that the labels do not overlap with each other and that they are close to the features they are associated with. However, this is not always possible to be achieved, for example, in the case where the labels are too large or the feature set is too dense. In this problem, the labels may be far from their features such that they are pairwise disjoint. But each feature should be connected to its associated label through a polygonal line including a straight line, called a connector. Clearly, the connectors should not intersect with each other. The connectors are only of two kinds. One consists of a single vertical line, called a straight connector and the other consists of three connected line segments, that is, vertical, horizontal, and vertical segments, called a bended connector. See Figure G.1.

Specifically, there is a straight line L, considered to be the x-axis, on which n points, corresponding to the point features, lie. The locations of the n points are strictly different. In this problem, the labels are considered as rectangular areas with height 1 on the plane. So each point pi is associated with an axis-parallel rectangular label li of width wi and height 1. Note that the heights of all the labels are identical. These rectangular labels should be pairwise disjoint, but the boundaries of two labels can be touched. Consider a line U which is parallel to L, above L, and has a vertical distance 1 from L. The labels li should be placed such that their lower sides are attached on U and they are above U as shown in Figure G.1.

Figure G.1 Rectangular labels of point features

You write a program to find the placements of labels such that the number of bended connectors is minimized. For example, for the point features and the labels given in Figure G.1, the placement of labels shown in Figure G.2 minimizes the number of bended connectors.

Figure G.2 Optimal placement of labels

문제풀이

사용한 알고리즘 : DP

(1) 코드 9~10

 아래에서 저는 0-indexed 로 생각할 것입니다. ( 이게 편해서요.... )

 'dp[x] : x 정점에서 처음으로 휘지 않는 connector을 연결하였고 (0~x-1 까지는 다 휘었다고 생각) x 에 대응하는 사각형의 우변을 x 정점 위치에 딱 맞게 배치 했을 때, x이상~N-1이하 정점의 bended connector의 최소 개수' 

 라고 설정하였습니다.

 

 위와 같이 dp를 설정하면 구하고자 하는 답은, 

 i + dp[i] 중 최소값 입니다. (0<= i <= N-1)    (0-indexed)

 i 정점에서 처음으로 휘지 않은 connector 을 연결하므로 i 이전의 0~i-1 정점 i개가 휜 connector로 연결되어 있음을 생각해보면 알 수 있습니다.

(2) 생각

 1. N<=2 이면 무조건 답은 0 입니다.

단적으로 위와 같이 배치하면 되겠죠...?

 2. N > 2 일 때는 0~N-1 의 모든 정점에 대해 dp[i] 값을 구합니다.

    

    임의의 dp[i] 값을 구할 때를 생각해 봅시다.

    [1] i 위치에 대응하는 사각형의 우변을 딱 맞춰 시작합니다.

        

 

    [2] i+1위치에 대응하는 사각형을 일단 이전 까지 채워진 위치에 붙입니다.

[2]-1. 이렇게 붙을 수 도 있고

[2]-2. 이렇게 붙을 수도 있겠죠

        이때마다 휘게 되는 connector 개수를 세주는 겁니다. ( 이하 cnt 개 )

        (즉, 대응되는 사각형의 왼쪽 변과 오른쪽 변 사이에 정점이 위치 하는지 여부 체크)

        이를 N-1 까지 진행해줍니다.

    [3] i~k까지 진행되었고 k+1번째 정점을 탐색할 때 다음과 같이 생각할 수 있습니다.

[3]-1. 이런 경우나

[3]-2. 이런 경우도 가능하고요

[3]-3. 이런 경우도 가능해요

        k+1 사각형을 대응시키는 상황은 위 그림 말고도 많은 경우가 있을 수 있습니다.

        이때 그림 [3]-3과 같이 대응되는 사각형의 우변이 정점 위치보다 왼쪽일 경우

        위 그림과 같이 대응되는 사각형의 우변을 k+1에 맞추는 경우를 추가적으로 생각해 줍니다.

        즉, i~k 정점까지 휜 connector 개수 cnt 에다가 dp[k+1]을 더한 경우가 

        dp[i]의 값이 될 수 있다는 점을 생각해주어야 합니다.

        그림 [2]-2 같이 시작부터 (i+1부터) 사각형의 우변이 정점 위치보다 왼쪽인 경우에도 

[2]-2.

        마찬가지로

        dp[i] = 0 + dp[i+1] 의 경우를 생각해주어야겠지요!

(3) 코드 12~35

 과정(2) 의 생각한 정점 idx에서의 dp[idx]값을 구하는 코드입니다.

 idx에 대응되는 사각형의 오른쪽 변을 딱 맞춰서 시작하여 N-1까지 탐색합니다.

 탐색을 진행하면서 휘는 connector 개수를 세어주고,

 각 탐색 시 대응되는 사각형의 우변이 해당 정점 위치보다 왼쪽일 때의 경우를 생각해줍니다.

(4) 코드 41~50

 N개의 정점이 작은 순으로 입력 되는게 아닐 수 있습니다. 이를 주의해야 됩니다.

 따라서 입력 받은 정점과 이에 대응되는 사각형을 묶어서 정점이 작은 순으로 재배열 해줍니다.

(5) 코드 57

 모든 정점의 dp 값을 구해줍니다.

(6) 코드 59~60

 가능한 최대 정답은 N 으로 설정하고 모든 정점에 대해 정답을 최신화 해주었습니다.

 사실 가능한 최대 정답은 N-2 일 것 같긴 합니다...

        

난잡한 문제 풀이지만, 그래도 조금의 도움이 되셨으면 좋겠습니다...