[python] 백준 2261 :: 가장 가까운 두 점 (분할 정복)
2023. 3. 14. 21:15ㆍAlgorithm
728x90
반응형
[가장 가까운 두 점]
# 문제
2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오.
# 입력
첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 있다.
# 출력
첫째 줄에 가장 가까운 두 점의 거리의 제곱을 출력한다.
💡 참고한 블로그 👉🏻 codable
1. 입력 받아서 x좌표를 기준으로 정렬한다.
- 점이 뒤죽박죽으로 주어지니까, 일단 정렬부터 하고 보자..
# n개의 점을 입력 받아 2차원 리스트로 저장
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
arr.sort() # x좌표를 기준으로 정렬
2. 두 점 사이를 구한다.
- 점이 음수일 수 있으므로 거리를 구하기 위해서는
(x 좌표 차이의 제곱 + y 좌표 차이의 제곱) ** 1/2
요로케 해주면 된다.
문제에서 거리의 제곱을 출력하라고 했으니 여기서** 1/2
는 노놉!def get_dist(a, b): # 두 점 사이의 거리를 구하는 함수 return (a[0]-b[0])**2+(a[1]-b[1])**2
3. 점의 개수에 따라 분기한다.
- 자 이제 최솟값 구하기 스타또-!
- 시작점과 끝점을 인자로 받아서 분할 정복으로 풀 것이다.
- start와 end의 차이가 0 또는 1이 될 때까지 쪼갤거임
start와 end의 차이가 0
- 반띵씩 줄어들다보면 같은 값이 시작점과 끝점으로 주어질 수도 있다.
이때는 거리를 계산할 수 없으니 결과값에 영향을 주지 않게sys.maxsize
를 때려버린당
def get_min(start, end):
if start == end: # 점이 하나인 경우, 최대값 반환
return sys.maxsize
start와 end의 차이가 1
- 점이 두 개일 때는 위에서 만들어 둔 함수로 두 점 사이의 거리를 구한다.
if end - start == 1: # 점이 두 개인 경우, 두 점 사이의 거리 반환 return get_dist(arr[start], arr[end])
start와 end의 차이가 0도 아니고 1도 아님
- 차이가 0이나 1이 되게 쪼개주자
mid = (start + end) // 2 # 중간 지점 계산
# 왼쪽 절반과 오른쪽 절반을 각각 재귀적으로 호출
min_dist = min(get_min(start, mid), get_min(mid, end))
4. mid 근처를 검증한다.
- 쪼개지는 부분에 절묘하게 답이 존재할 수도 있다.
그래서 쪼개지는 부분도 검증해줘야 한다. 🙁😠 - 위에서 일단
min_dist
를 구했으니까,
쪼개진 지점인arr[mid]
를 중심으로 왼쪽 오른쪽으로-min_dist ~ +min_dist
범위 안에 드는 점들만 찾아서candidates
에 모은다. - 범위 안에 드는 점들만 찾기 👉🏻
(arr[mid][0] - arr[i][0])**2 < min_dist
💡 이 거리가 제곱되어있는 값이라는 것 잊지말자
# 가운데 점(mid)을 기준으로 거리가 min_dist보다 작은 점들을 candidates 리스트에 추가
candidates = []
for i in range(start, end+1):
if (arr[mid][0] - arr[i][0])**2 < min_dist:
candidates.append(arr[i])
- 범위를 또 줄여주기 위해서 y좌표를 기준으로 정렬한다.
# candidates 리스트를 y좌표를 기준으로 정렬 candidates.sort(key=lambda x: x[1])
- 아래점에서 위에 위치하는 애들만 계산을 해본다.
# candidates 리스트 내에서 최소 거리를 구함
for i in range(len(candidates)-1):
for j in range(i+1, len(candidates)):
- 위에서
candidates
를 만들 때 했던 것처럼, y좌표도 차이의 제곱이min_dist
를 넘어가면 반복을 멈춘다. (어차피 더 멀어서 볼 것도 없음😋)
# y좌표 차이가 min_dist보다 작은 경우에만 최소 거리 계산
if (candidates[i][1] - candidates[j][1])**2 < min_dist:
min_dist = min(min_dist, get_dist(
candidates[i], candidates[j]))
else:
break
끝😘
전체 코드
import sys
n = int(input())
# n개의 점을 입력 받아 2차원 리스트로 저장
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
arr.sort() # x좌표를 기준으로 정렬
def get_dist(a, b): # 두 점 사이의 거리를 구하는 함수
return (a[0]-b[0])**2+(a[1]-b[1])**2
def get_min(start, end):
if start == end: # 점이 하나인 경우, 최대값 반환
return sys.maxsize
if end - start == 1: # 점이 두 개인 경우, 두 점 사이의 거리 반환
return get_dist(arr[start], arr[end])
mid = (start + end) // 2 # 중간 지점 계산
# 왼쪽 절반과 오른쪽 절반을 각각 재귀적으로 호출하여 최소 거리를 구함
min_dist = min(get_min(start, mid), get_min(mid, end))
# 가운데 점(mid)을 기준으로 거리가 min_dist보다 작은 점들을 candidates 리스트에 추가
candidates = []
for i in range(start, end+1):
if (arr[mid][0] - arr[i][0])**2 < min_dist:
candidates.append(arr[i])
# candidates 리스트를 y좌표를 기준으로 정렬
candidates.sort(key=lambda x: x[1])
# candidates 리스트 내에서 최소 거리를 구함
for i in range(len(candidates)-1):
for j in range(i+1, len(candidates)):
# y좌표 차이가 min_dist보다 작은 경우에만 최소 거리 계산
if (candidates[i][1] - candidates[j][1])**2 < min_dist:
min_dist = min(min_dist, get_dist(
candidates[i], candidates[j]))
else:
break
return min_dist
print(get_min(0, n-1))
728x90
반응형
'Algorithm' 카테고리의 다른 글
[python] 백준 2014 :: 소수의 곱 (우선순위 큐) (0) | 2023.03.16 |
---|---|
[python] 백준 6549 :: 히스토그램에서 가장 큰 직사각형 (스택) (0) | 2023.03.14 |
[python] 백준 10000 :: 원 영역 (스택) (1) | 2023.03.14 |