[백준] 17371 - 이사

www.acmicpc.net/problem/17371

17371번: 이사

 

그리디 알고리즘 연습문제로 풀게된 '이사' 문제이다.

고민끝에 다른 분의 풀이를 봤다.

 

burningjeong.tistory.com/293

17371 이사

그런데 미천한 내 이해력으론 이 분의 풀이 설명을 봐도 이해가 안됐다.

그래서 이 분의 소스코드를 읽고 문제를 보고 교차비교해가며 이해했다.

 

이 문제의 핵심은 다음 부분이다.

 

"그나마 좌표를 찾기 쉽도록

가장 가까운 편의시설까지의 거리와 가장 먼 편의시설까지의 거리의 평균이

최소가 되는 좌표로 이사하려고 한다."

 

결론적으론 이 말을 그대로 구현해서 이 문제를 풀 수 있다.

N=1000 이기 때문에, 1000개의 점들 간의 거리를 나이브하게 모두 구해도

1,000 * 1,000 = 1,000,000 이기 때문에 모든 거리를 다 체크할 수 있다.

가장 가까운 편의시설부터 가장 먼 편의시설까지의 거리 평균을 다 구해서 그 중에 최소를 찾으면 된다.

하지만 편의시설간 거리와 집의 좌표가 어떤 관계가 있는지는 바로 이해하기 힘들다.

그 관계성을 찾아보자.

 

이 문제의 답으로 출력해야 하는 것은 '가장 짧은 거리가 되는 좌표' 이다.

그런데 사실 좌표값 자체는 중요하지 않다.

 

문제의 출력란을 보자.

 

첫 번째 줄에 혜아가 이사할 곳의 좌표 (Hx, Hy)를 나타내는

두 실수 Hx, Hy를 공백 하나로 구분하여 출력한다.

가장 가까운 편의시설까지의 거리와 가장 먼 편의시설까지의 거리의 평균을

정답과 비교했을 때 절대오차 혹은 상대오차가 10-6 이하면 정답으로 인정한다.

 

출력해야하는 값이 좌표이다보니

나도 모르게 좌표를 구하려고 고민하던 과정에서 막혔던 점이 컸다.

 

좌표는 여러개가 될 것 같은데 어떻게 구해야하지? 식을 세워서 계산해야하나?

이런 생각에 빠져서 헤어나오질 못했다.

 

일정 오차이하 + 예제 출력 좌표에 6자리 소수점 표기까지, 문제를 대충 읽으면 당하기 쉬운 것 같다

하지만 사실 이 문제에서 요구하는 것은 좌표가 아닌 거리이다.

 

출력한 좌표로부터 가장 가까운 편의점과 가장 먼 편의점 사이의

거리 평균값이 원래 정답과 일정 오차이하이면 되는 것이다.

그렇다면 어차피 거리의 평균값의 최소를 구해야하는 것이고,

 

평균값이라 함은

(가장 가까운 거리 + 가장 먼 거리) / 2 인데

사실 거리를 출력하는 것이 아니기 때문에, / 2는 계산할 필요도 없이

(가장 가까운 거리 + 가장 먼 거리) 가 최소가 되는 좌표를 아무거나 출력하면 된다.

 

이제 여기에서 생각을 단순하게 해볼 수 있다.

문제 조건에서

 

이 좌표계에는 그 어떤 위치에도 주거할 수 있는 시설이 있기 때문에

혜아는 두 실수 Hx, Hy 를 골라 좌표 (Hx, Hy)로 이사할 것이다.

 

라고 했다.

그렇다면 편의시설 위에 집이 있어도 상관이 없다.

그럼 가장 가까운 거리는 이제 생각할 필요가 없어졌다.

편의시설 위치를 집의 위치라고 하면 가장 가까운 거리는 0이기 때문이다.

 

그럼 한 편의시설을 골라 그 편의시설 위치에 집이 있다고 가정하고

그 편의시설의 위치로부터 가장 먼 편의시설의 값을 구하면

문제에서 요구하는 (집에서 가장 가까운 편의시설까지 거리 + 가장 먼 편의시설까지 거리) 를 한번에 구할 수 있다.

 

( 0 + 집으로부터 가장 먼 편의 시설까지 거리 )

= (내가 선택한 편의시설로부터 가장 먼 편의시설까지의 거리)

 

편의 시설은 N개가 있으니, 총 N개의 값을 구할 수 있을 것이다.

그리고 이 값들 중 가장 작은 값을 찾으면 된다.

그럼 집의 좌표는 어떻게 될까?

"가장 작은 값을 갖게 만든 가장 가까운 편의시설의 위치"

= "거리를 구할 때의 기준 위치"를 출력하면 된다.

집으로부터 가장 가까운 편의시설까지 거리를 0으로 가정했기 때문이다.

 

파이썬으로 내가 제출한 코드는 다음과 같지만,

위에 소개한 분의 코드로 그 분의 아이디어를 이해하고나니

사실상 그 분의 코드를 파이썬으로 옮긴 것에 지나지 않게 되었다.

# 17371 이사
import sys

def distance(x1, y1, x2, y2):
    return (x2-x1)**2 + (y2-y1)**2
    
n = int(input())
convini = []

for _ in range(n):
    convini.append(tuple(map(int, sys.stdin.readline().split())))

_min = 9876543210
_min_idx = -1

for i in range(n):
    _max = -1
    _m_idx = -1
    for j in range(n):
        d = distance(convini[i][0], convini[i][1], convini[j][0], convini[j][1])
        if _max < d:
            _max = d
            _m_idx = i
    if _max < _min:
        _min = _max
        _min_idx = _m_idx
        
print(convini[_min_idx][0], convini[_min_idx][1])

 

문제를 풀다가 문득, 그냥 모든 편의시설 사이의 거리를 모두 구해서

그 중 가장 짧은 값을 구하면 더 효율적이지 않을까? 하는 생각도 했었다.

 

어차피 다 정리하면 O(n^2)의 시간복잡도 인 건 똑같지만,,

n^2으로 다 구하는 것보다 nC2의 조합으로 구하는게 더 효율적이라고 생각했다.

 

하지만 nC2로 구하게 되면 문제가 발생한다.

어느 점이 기준점인지 알 수가 없는 점이다.

이 문제에서는 (n, k) 를 n번째 편의시설부터 k번째 편의시설까지 거리라고 했을 때

(n, k)와 (k, n)이 갖는 값은 같을지 몰라도, 이 둘이 의미하는 것은 전혀 다르다.

 

(n, k) 는 n번째 편의시설에 집이 있다고 가정할 때의 거리이고

(k, n) 은 k번째 편의시설에 집이 있다고 가정할 때의 거리이다.

이 둘을 같은 것으로 취급하면 어떤 편의시설에 집이 있었는지를 알 수 없게된다.

따라서 단순하게 조합만 사용해서는 답을 찾을 수 없다.

(미리 기억해놨다가 갖다 쓰는 건 가능하겠지만,

오히려 공간복잡도 낭비에, 코드만 더 복잡해질 것 같다고 생각한다.)

 

burningjeong.tistory.com/293

17371 이사

마지막으로 위에 소개한 분의 링크를 다시 달면서 문제 정리를 마친다.