[파이썬/python] 백준 28215 - 대피소

문제

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

---

문제 설명

1. KOI 마을에는 N개의 집이 존재하며 N개의 마을 중 K개의 대피소를 뽑는다.
2. 각각의 집과 대피소와의 거리를 계산한다나머지 집들 중 대피소와 가장 거리가 먼 집과 대피소와의 거리가 최소가 되도록 대피소를 선택한다.

두 좌표 사이의 거리 계산식: $|X_2 - X_1 | + |Y_2 - Y_1 |$

 

$N=5$일 때 $(1,5)$, $(3,0)$, $(3,3)$, $(6,12)$, $(8,9)$위치에 집이 존재한다고 가정하자.

1. 대피소의 위치가 $(3,0)$, $(1,5)$일 때

	$(3,0)$	$(1,5)$	최솟 값
$(3,3)$	$3$	$4$	$3$
$(6,12)$	$15$	$12$	$12$
$(8,9)$	$14$	$11$	$11$

각 집에서 대피소와의 거리의 최소는 3,12,11 이므로 대피소와 가장 먼 집의 거리는 12이다.

2. 대피소의 위치가 $(3,3)$, $(6,12)$일 때

	$(3,0)$	$(1,5)$	최솟 값
$(1,5)$	$4$	$12$	$4$
$(3,0)$	$3$	$15$	$3$
$(8,9)$	$11$	$5$	$5$

각 집에서 대피소와의 거리의 최소는 4,3,5 이므로 대피소와 가장 먼 집의 거리는 5이다.

 

---

풀이

브루트포스 알고리즘을 통해 대피소가 선택될 수 있는 모든 경우의 수를 확인한다.

1. N개의 집들 중 K개의 대피소를 선택한다.(조합)
2. 각각의 집과 대피소와의 거리를 계산한 후 집 별 대피소와의 거리 최솟값을 갱신한다.
3. 집 별 거리 최솟값 중 가장 먼 집의 거리를 찾는다.
4. 가장 먼 집의 거리의 최솟값을 갱신한다.

---

코드

import sys
import math
from itertools import combinations
input = sys.stdin.readline

N,K = map(int,input().split())
house = []
INF = math.inf
for i in range(N):
    x,y = map(int,input().split())
    house.append([x,y])

def cal_dist(cur_house, shelter):
    return abs(house[cur_house][0]-house[shelter][0]) + abs(house[cur_house][1]-house[shelter][1])



max_dist = INF

for shelters in list(combinations(range(N),K)): # 대피소 K개를 선택
    cur_dist = -1

 # 집 별 대피소와의 거리를 계산한다.
    for cur_house in range(N):
        cur_house_dist = INF
        for shelter in shelters:
            cur_house_dist = min(cur_house_dist, cal_dist(cur_house, shelter))
        cur_dist = max(cur_dist, cur_house_dist)
    max_dist = min(max_dist, cur_dist)
print(max_dist)

---

시간복잡도

• 시간 제한: 3초, 약 $O(3*10^8)$
• N개의 집 중 K개를 선택하는 시간복잡도: $O(_nC_k)$
• 집 별 대피소와의 거리 계산 시간복잡도: $O((N-K)*K)$
• 총 시간복잡도: 약 $O(_nC_k * N*(N-K))$
• 최악일 때 시간복잡도: $N=50$, $K=3$일 경우 $O(_{50}C_3 * 50 * 47) = 4*10^7$