백준 5620번 파이썬 풀이: 가장 가까운 두 점의 거리

백준 5620번 가장 가까운 두 점의 거리

 

알고리즘 분류: 기하학, 분할 정복, 스위핑

 

링크: https://www.acmicpc.net/problem/5620

 

5620번: 가장 가까운 두 점의 거리

문제

평면상에 n개의 점 (P1, .... ,  Pn) 이 놓여져있다고 했을 때, 거리가 최소인 두 개의 점을 구하고 그 거리를 알고 싶다.

입력

입력은 첫 번째 줄에 정수로 된 점의 개수 n이 주어진다.

두 번째 줄부터 n+1번째 줄까지 2개의 정수 x,y가 공백을 사이에 두고 주어진다. 

i+1번째 줄은 Pi 의 x,y 좌표를 의미하고 n개의 점에 대해서 주어지게 된다.

점의 개수는 2 ≦ n ≦ 500000 , 좌표의 범위는 -10000 ≦ x,y ≦10000로 주어진다.

또한, 모든 점의 좌표는 같은 것이 없이 다른 것으로 한다.

출력

가장 가까운 두 점 사이의 거리의 제곱을 출력하시오.

 

문제 파악

 

결론부터 말하면 이 문제 역시 풀지 못했습니다..

 

알고리즘 분류가 분할 정복으로 되있지만 브루트 포스외에는 생각이 나질 않아서 시도했으나

 

역시나 시간초과로 틀렸습니다.

 

그럼에도 불구하고 이 문제를 블로그에 올리는 것은 다른 분의 코드를 보고 배우려고해도

 

이 문제를 파이썬으로 푸는 방법이 검색해도 많이 나오지 않기 때문에

 

혹시나 실력좋으신 분들이 한번씩 들려가면서 힌트를 주실까해서 올려봅니다.

 

코드

 

저는 모든 경우의 수를 다 대입해보는 브루트포스 알고리즘을 이용했습니다.

 

인풋값을 저장해놓은 location_list를 coordinates라는 파라미터로 사용하여서

 

pair(가장 가까운 두점)의 처음 초기값을 coordinates의 0번인덱스와 1번인덱스로 놓고

 

for문을 이중으로 돌면서 coordinates의 인덱스들을 location1,2로 놓는데 이 과정에서

 

a, b = c, d 이런식으로 쓰는 파이써닉한 코드를 사용하였다.

 

location1,2의 거리가 pair의 거리보다 짧다면 pair를 location1,2로 교체해준다.

 

for문을 다 돌고나면 가장 가까운 두 점인 pair를 리턴해주고

 

마지막으로 pair의 0번 인덱스와 1번 인덱스의 거리의 제곱을 출력해준다.

 

이런 방식으로 풀이를 해보았는데 아무래도 점의 개수가 50만개까지 주어지고 하다보니

 

브루트포스 알고리즘으로는 시간초과가 날 것이다.

 

알고리즘의 분류가 분할 정복으로 되어있어서 분할 정복으로 어떻게 풀까 고민을 해보았는데

 

도저히 어떻게 풀어야할지 생각을 못해내서 구글에 검색해보아도 정보가 많이 없어서

 

블로그에 글을 올려서 다른 사람들의 도움을 받고 싶었다.