[백준] 24616. Moo Network

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

문제요약

• 소들의 좌표가 주어지고, 모두 연결할 수 있는 최소 비용 구하기
• x : 1000000, y : 10, n : 100000
• 거리 : x^2 + y^2 거리

접근법

• MST를 사용하는 것은 알겠음. 크루스칼은 무리가 있음. 프림도 무리가
  있어 보임
• 왜 y 범위가 10일까?
  • 전체적인 모양은 y폭은 좁고 x축으로 넓게 퍼진 모양일 것임
  • 모든 점의 거리를 구할 필요는 없겠다
• 가장 왼쪽에 있는 점도 어딘가와 연결을 해야할 것임
  • 근처에 있는점만 보아도 됨
  • 굳이 오른쪽 끝에 있는 점과의 거리를 고려하지 않아도 됨
  • x 좌표 기준으로 +, - 특정 범위 내에만 고려해볼 수 있겠음
• +, - 특정범위를 어떻게 고려함?
  • 그 범위 안에 점들이 적당히 있을 수도 있겠지만, 아예 없을 수도 있음
  • 점들이 있어도, 더 가까운 점을 놓칠 수도 있음
    
  • x값이 아닌 점의 개수로 봐야할 것 같음
• 점이 가장 빽빽하게 차있더라도 10 x 10 영역 내의 점들을 다 살필 수 있다면 가장 가까운 점을 찾을 수는 있을 것임
• 가장 왼쪽 점부터 연결을 해 나간다고 할때 이후 100개 정도만 살피면 될 것 같음
• 이때 이전 100개도 살펴야 함
  • 빨간 점의 경우 왼쪽에서 보다 오른쪽 점에서 더 가까운데, 오른쪽점의 뒷부분에 있음
    

구현

• 프림 알고리즘을 사용하고,
• 확인하는 간선은 앞/뒤 100개만 확인함
• 이를 위해 점을 x 좌표 기준으로 정렬하고
• x 좌표들이 처음 나타나는 offset을 구해놓음
• offset 기준으로 offset - 100 ~ offset + 100 사이의 점을 대상으로 간선의 길이를 구함