분할정복. [2261]

[1. 문제 설명]

https://www.acmicpc.net/problem/2261

---

[2. 풀이 접근]

주의 사항

• 중복되는 점을 제거해서는 안된다.
  => 같은 점이 있다고 했을 때, 모든 점들 간 최소 거리는 0 이 되는 것이 맞기 때문이다.
  => 중복되는 점을 제거하면 이러한 경우는 찾을 수 없다.

분할 정복 및 스위핑으로 접근해야 한다.

먼저 분할 정복을 사용하는 이유이다.

1. x 를 기준으로 정렬 후, 모든 경우의 수를 찾는 다면, 그 시간 복잡도는 O(N²) 이므로 시간 내 풀 수 없다.
2. 분할 정복 패턴을 적용한다.
   =>  재귀로 구현하므로 기저 사례를 먼저 작성한다.
   =>  기저 사례는 [head, tail] 구간의 길이가 2인 경우, 즉 두 개 의 점간 거리를 반환한다.
   =>  head ~ mid 구간에 대해 재귀 호출 한다.
   =>  mid+1 ~ tail 구간에 대해 재귀 호출 한다.
   =>  head ~ tail 구간에 대한 문제를 해결 한다.

이 문제에서 핵심은 바로 재귀 호출 이후 [head, tail] 구간에 대한 문제를 풀이하는 것이다.

처음에는 아래 히스토그램 문제 처럼 접근해보았다.

• https://testkernelv2.tistory.com/512

아직 확인해보지 않은 mid 와 mid+1 의 좌표에 대해서 거리를 계산하고,

왼쪽, 오른쪽 중 어느 곳으로 가야하는지 결정해보는 방식이다.

그러나 이 풀이는 틀렸다.

정확한 이유는 모르겠다.

 

그래서 다음의 두 풀이를 참조하였다.

1. https://casterian.net/algo-prob/boj2261.html
2. https://hackids.tistory.com/61

정리하면, [head, tail] 에서 중간 좌표를 기준으로 dx 만 따졌을 때,

분할정복으로 구한 거리보다 크면 이 점은 답의 후보가 될 수 없으므로 완전 탐색 범위에서 제외한다.

그리고 완전 탐색 대상으로 할 점 (왼쪽 구간과 오른쪽 구간 점들의 조합이 될 후보) 들은

x,y 를 뒤집어서 저장한다.

 

x 를 기준으로 dx 를 따져보았으므로,

y 를 기준으로 dy 를 구해 가지치기 해볼 수 있기 때문이다.

 

이렇게 양쪽 구간의 점 중에서 답이 될 수 있을 만한 후보끼리는 완전 탐색을 진행한다.

단, dy 가 기존 최소거리보다 같거나 크다면 이 이후로는 답이 될 가능 성이 없으므로

탐색을 중단 할 수 있다.

---

[3. 코드]