[백준] 28215번 대피소 파이썬 코드

코드

import sys
from itertools import combinations

INF = 987654321
input = sys.stdin.readline

def dist(x1, y1, x2, y2):
  return abs(x1 - x2) + abs(y1 - y2)

n,m = map(int, input().split())
coor = [] # 좌표를 넣을 리스트
res = INF
for _ in range(n):
  x,y = map(int, input().split())
  coor.append((x,y))

for i in combinations(coor, m):
  temp = 0
  for j in coor:
    min_dist = INF # 가장 가까운 대피소 찾아주는 과정
    for k in range(m): 
      distance = dist(*i[k], *j)
      min_dist = min(min_dist, distance)
    temp = max(temp, min_dist) # 대피소 거리가 가장 먼 집을 찾아주는 과정
  res = min(res, temp) # 가장 먼 집 중에 가장 가까운 것을 찾는 과정
print(res)