(Python/파이썬) - 백준(BOJ) 17371번 : 이사

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

17371번: 이사

---

• 문제 : 

혜아는 답답한 3차원 세계를 벗어나 자유로운 2차원 좌표계 위로 집을 옮길 계획이다. 이 좌표계에는 그 어떤 위치에도 주거할 수 있는 시설이 있기 때문에 혜아는 두 실수 Hx, Hy 를 골라 좌표 (Hx, Hy)로 이사할 것이다.

 

이사할 집의 위치를 결정하기 위해 절대적으로 중요한 것은 편의시설이 집으로부터 얼마나 멀리 떨어져 있느냐는 점이다. 좌표계에는 N개의 편의시설이 있는데, 좌표계의 주거지역 정책에 따라 x, y 좌표가 모두 정수인 곳에만 편의시설이 있다.

 

혜아는 N개의 편의시설로 이동하는 데 드는 거리의 평균값이 최소가 되는 좌표로 이사를 가고 싶었지만, 이런 좌표를 찾는 것이 너무 어렵다는 것을 깨달았다. 그래서 그나마 좌표를 찾기 쉽도록 가장 가까운 편의시설까지의 거리와 가장 먼 편의시설까지의 거리의 평균이 최소가 되는 좌표로 이사하려고 한다. 이 좌표계에서 거리는 유클리드 거리를 사용하여, 두 좌표 (Ax, Ay)와 (Bx, By) 사이의 거리는 아래의 수식으로 나타낸다.

이 때, 혜아를 도와 가능한 위치 중 하나를 구해 주는 프로그램을 작성해보자.

 

 

 

---

• 풀이 :

수학 구현 문제였습니다.

 

문제를 푸는데 특별한 알고리즘은 필요하지 않았으나 아이디어를 생각해내지 못해 다른 사람의 풀이를 참고하여 해결하였습니다.

 

문제 해결의 핵심 아이디어는 "편의시설과 집의 좌표가 같을 수 있다."는 것입니다.

 

알고리즘의 흐름입니다.

 

1. 편의시설 좌표를 loc 배열에 저장. 이 때, 좌표들을 N^2 탐색한다.

 

2. h1은 집의 좌표를, h2는 가장 먼 거리의 편의시설을 찾는 용도이다.

 

3. 각 h1마다 모든 loc의 좌표를 찾으며 가장 먼 편의시설까지의 거리와 그 때의 편의시설 좌표를 구한다.

 

4. 가장 먼 편의시설까지의 거리들 중 최소를 갖고 있는 h1으로 정답을 갱신하여 출력한다.

 

 

추가 ) 지금 생각해보니 m은 그냥 거리만 들어있어도 문제를 해결하는데 지장이 없습니다. 굳이 [거리, 좌표]의 list로 이용하지 않아도 됩니다.

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

def distance(h1,h2):
    return (h1[0]-h2[0])**2 + (h1[1] - h2[1])**2

N = int(input())
loc = [tuple(map(int,input().split())) for _ in range(N)]
answer = [float("inf"),(0,0)]
for h1 in loc: # 가장 가까운 편의시설과 집 위치 후보
    m = [0,(0,0)]
    for h2 in loc: # 가장 먼 편의시실 후보
        if h1 != h2: # 같은 좌표는 제외
            d = distance(h1,h2)
            if d > m[0]: # 가장 먼 거리의 편의시설을 찾음
                m = [d, h2]
    if answer[0] > m[0]: # 가자 먼 거리의 편의시설의 거리들 중 최소가 정답
        answer = [m[0],h1]

print(answer[1][0], answer[1][1])