[백준 28215] 대피소 파이썬

종류: 브루트 포스

문제출처: 대피소

"KOI 마을의 집들의 위치와 설치할 대피소의 개수가 주어질 때, 대피소를 설치하는 모든 방법 중 가장 가까운 대피소와 집 사이의 거리 중 가장 큰 값이 가장 작을 때의 거리를 구해라."

문제 이해
🛖 N=집 수, K=대피소 수
🛖 대피소는 집들 중에 있다..!

순서
1.가능한 대피소 조합 만들기
2.집을 for문으로 해서 가장 가까운 대피소 찾아 거리 확정
3.모든 집에서 대피소 거리중 가장 큰 값 저장
4.(모든 대피소 조합) 3번 값들 중 가장 작은 값 출력

💎 **KEY POINT**

1. X, Y는 각각 따로 저장!
2. 최소값을 저장하는 변수에는 float("INF") 로 초기화
3. 최소, 최대 비교는 if문 보다 min, max 활용!

내가 작성한 코드

from itertools import combinations
N, K = map(int,input().split())
x = [0] * N
y = [0] * N
for i in range(N):
   x[i], y[i] = map(int,input().split())

comb = list(combinations(range(N),K)) # 집의 위치가 x,y 2차원이지만 한 묶음으로 생각하고 집들의 조합을 만들어 낸다. 이 집들 중에서 어떤 집을 대피소로 할 것인가
INF  = float("INF")  #key point
re=INF

for c in comb:
   case = 0
   for home_idx in range(N): #집에서 가장 가까운 대피소 찾기
       distance = INF
       for hide in c:
           tmp = abs(x[home_idx]-x[hide])+abs(y[home_idx]-y[hide])
           distance = min(tmp, distance)  #key point : 대소비교는 min/max로 
       case = max(case, distance)
   re = min(re,case)
print(re)

⏰ 700ms 시간 절약 코드

1. 함수형으로 바꿨다. 문제를 한번에 다 해결하는 것보다 큰 틀을 잡고 함수를 채워 나가자!
2. cobination(조합)을 list로 변경하지 말고 바로 사용!

from itertools import combinations
N, K = map(int,input().split())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int,input().split())

INF  = float("INF")  #key point

def dist(c):
    b=0
    for h_idx in range(N):
        a=INF
        for c_idx in c:
            tmp = abs(x[h_idx]-x[c_idx])+abs(y[h_idx]-y[c_idx])
            a = min(a,tmp)
        b = max(b, a)
    return b 

final = INF
for c in combinations(range(N),K):
    final = min(final,dist(c))
print(final)

Ref.
https://wikidocs.net/212464