파이썬 백준 2261 가장 가까운 두 점

import sys   input = sys.stdin.readline l = [] n = int(input()) for i in range(n) :     l.append(list(map(int, input().split()))) l.sort() def length(p, q) :     return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2 def DAC(start, end) :     if end == start + 1 :         return length(l[start], l[end])     center = (start + end) // 2     minl = min(DAC(start, center), DAC(center, end))         rng = []     for i in range(start, end + 1) :         if (l[center][0] - l[i][0]) ** 2 < minl :             rng.append(l[i])     rng.sort(key = lambda x : x[1])     for i in range(len(rng)) :         for j in range(i + 1, len(rng)) :             if (rng[i][1] - rng[j][1]) ** 2 < minl :                 minl = min(minl, length(rng[i], rng[j]))             else :                 break     return minl print(DAC(0, n-1))

인접한 두 점의 비교가 될때까지 재귀하여 문제를 쪼갠다.

이 바닥 상태의 문제는 쉽게 해결할 수 있다. (그냥 두 점의 거리 측정)

이전 레벨의 문제가 해결되었다면 그 리턴을 참고하여 불필요한 경우의 수를 쳐내는 거름망을 치고, 그 안에서만 탐색하여 빠르게 결과를 낸다. 그리고 그 결과를 다음 레벨의 위해 리턴. 이를 반복하는 함수를 재귀호출 밑에 구현한다.

문제에선 길이 2min의 range를 치고, 그 안에서도 y거리가 min 이하인 점끼리만 비교하는 식의 거름망을 쳤다.

이를 실행하면, 먼저 바닥까지 재귀한 뒤 쉽게 해결한 바닥 상태의 문제로부터 점점 레벨을 높여가며 마지막으로 본문제가 해결된다.

 

DFS : 문제가 해결이 안된다면 -> 될 때까지 쪼개며 내려간다 -> 바닥 전에 해결될 수도 있고 안될 수도 있음

DAC : 안될게 뻔하니 일단 바닥까지 쪼개자 -> 쪼갠 부분에서 해결한 결과를 이용해 더 큰 부분의 문제를 해결

DFS가 해가 자명하게 구해질 때까지 재귀를 반복하며 문제를 단순화한다면, DAC는 서순이 반대인 셈.

 

그동안 DAC 문제를 풀면서도 이거 그냥 DFS가 아닌가 싶었는데,

일단 최소단위까지 쪼개지 않으면 답이 안나오는 문제를 접하니 둘의 차이가 감이 잡히는 것 같다.