[Python] 백준 28215번 대피소

문제

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

 

입력 예제

5 2
1 5
3 0
3 3
6 12
8 9

4 2
0 0
0 5
5 0
5 5

출력 예제

5

5

문제 풀이

• 조합으로 k개의 집에 대피소 설치
• 각 집에서 최소거리가 걸리는 대피소 찾기
• 가장 가까운 대피소에서 멀리 떨어진 거리 찾기
• 먼 거리중 최소거리 걸리는 대피소 찾은 후 출력

코드

from itertools import combinations
n,k = map(int,input().split())
house = []
for _ in range(n):
    x,y = map(int,input().split())
    house.append([x,y])

# 모든 집과의 거리가 가장 가까운 대피소 찾기
list = [[] for _ in range(n)]
result = float('INF')
for c in combinations(house, k):
    tmp = []
    max_val = 0
    for h in range(n):
        home = house[h]
        min_val = 99999999
        for cc in c:
            distance = []
            tmp_val = abs(home[0] - cc[0]) + abs(home[1] - cc[1])
            min_val = min(min_val, tmp_val)
        max_val = max(min_val, max_val)
    result = min(max_val, result)

print(result)

---

값을 바로바로 찾지 않고 계속해서 배열을 선언해서 문제를 처리했는데, 이런 식으로 바로 값을 비교하는 게 더 간단하다.