9763. 마을의 친밀도

문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 보러 가기

접근 과정

최초에는 세 마을이라는 것을 생각해 O(N^3)의 풀이를 떠올렸지만, 주어지는 마을의 수 N이 10000까지인 것을 보고 O(N^3)의 풀이로는 해결할 수 없는 문제라고 생각하게 되었다.

문제를 다시 읽어보며 알게 된 점은, 세 마을의 친밀도를 구하는 과정에서 한 마을이 2번 들어간다는 것이었다!

친밀도 = d12 + d23 (dij = |xi - xj| + |yi - yj| + |zi - zj|)

여기에서, d2 마을은 2번 들어간다. (d12 + d23)

따라서, 한 마을을 기준으로 잡고, 기준 마을과 나머지 두 마을간의 거리를 구해가며 얻은 최소의 값이 가장 작은 세 마을의 친밀도임을 알 수 있었다.

정리하면...

• 주어진 정수 N까지 순회하는 반복문을 통해 매 순회마다 마을 하나를 기준으로 잡는다.
  • 내부에서 다시 동일 범위의 반복문을 사용하고, 바깥 반복문에서 기준으로 잡은 마을과 내부 반복문에서 순회하며 만나는 마을간의 거리를 계산한다.
  • 이렇게 한 마을을 기준으로 한 세 마을의 최소 친밀도를 구한다.
  • 외부 반복문에서 한 번의 순회가 끝날 때마다, 최솟값 연산을 통해 전체 마을 기준 세 마을의 최소 친밀도를 구한다.

풀이

import sys

input = sys.stdin.readline
N = int(input())
vil = [list(map(int, input().split())) for _ in range(N)]
ans = 0xffffff
for i in range(N):
    former, after = 0xffffff, 0xffffff
    for j in range(N):
        if i != j:     # 동일한 마을을 선택하지 않게 하기 위한 조건문
            temp = abs(vil[i][0] - vil[j][0]) + abs(vil[i][1] - vil[j][1]) + abs(vil[i][2] - vil[j][2])
            
            # 두 마을간의 친밀도를 구한 후, 이 중 최소값, 2번째 최소값을 각각 former, after에 저장한다.
            # 이는 former 마을 - i번째 마을 - after 마을 으로 세 마을의 친밀도 최소값을 구할 수 있게 한다.
            if former > temp:
                after = former
                former = temp
            elif after > temp:
                after = temp
    
    # 내부 반복문을 전부 순회하고 나서, 현 시점에서의 최소 친밀도를 구한다.
    ans = min(ans, (former + after))
else:
    print(ans)

통과!

읽어주셔서 감사합니다!