그리디 알고리즘 연습문제로 풀게된 '이사' 문제이다.
고민끝에 다른 분의 풀이를 봤다.
그런데 미천한 내 이해력으론 이 분의 풀이 설명을 봐도 이해가 안됐다.
그래서 이 분의 소스코드를 읽고 문제를 보고 교차비교해가며 이해했다.
이 문제의 핵심은 다음 부분이다.
"그나마 좌표를 찾기 쉽도록
가장 가까운 편의시설까지의 거리와 가장 먼 편의시설까지의 거리의 평균이
최소가 되는 좌표로 이사하려고 한다."
결론적으론 이 말을 그대로 구현해서 이 문제를 풀 수 있다.
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번째 편의시설에 집이 있다고 가정할 때의 거리이다.
이 둘을 같은 것으로 취급하면 어떤 편의시설에 집이 있었는지를 알 수 없게된다.
따라서 단순하게 조합만 사용해서는 답을 찾을 수 없다.
(미리 기억해놨다가 갖다 쓰는 건 가능하겠지만,
오히려 공간복잡도 낭비에, 코드만 더 복잡해질 것 같다고 생각한다.)
마지막으로 위에 소개한 분의 링크를 다시 달면서 문제 정리를 마친다.
'알고리즘 (PS) > BOJ' 카테고리의 다른 글
[백준] 5719 - 거의 최단 경로 (0) | 2021.04.17 |
---|---|
[백준] 2662 - 기업 투자 (0) | 2021.04.06 |
[백준][C++] 9935 문자열폭발 (0) | 2021.02.13 |
[백준][C++] 19541 루머 (0) | 2021.02.08 |
[백준][Python3] 20500 - Ezreal 여눈부터 가네 ㅈㅈ (0) | 2021.01.24 |