Baekjoon 28215 | 대피소 (Python)

📌문제

SILVER4 / 브루트포스 / 완전탐색 / 구현 / 알고리즘

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

📌문제 분석 및 설계

역대급 바보짓한 문제다.. 문제이해부터 알고리즘 구현까지 30분만에 해놓고 초기화잘못된 거 못 찾아서 1시간30분을 날렸다 하핳

 

아무튼, 문제 읽었을때 조합 함수 사용하고 완탐하면 되겠구나 ! 하고 바로 알고리즘을 작성했다.

 

나의 실수는 result를 -1로 초기화를 했다는 것이었다.

모든 집이 대피소로 지정되는 예외사항을 고려를 하지 못한 것이다.

결국 모든 집이 대피소로 지정되는 경우 other not in daepi 조건이 항상 False가 되어, result가 그대로 -1인 상태로 남아버려서 계속 틀렸다.

다들 조심.

 

📌소스 코드

import math
from itertools import combinations
def distance(i,j):
    return abs(i[0]-j[0])+abs(i[1]-j[1])

n,k=map(int,input().split()) #n개 집, k개 대피소
home=[]
for _ in range(n):
    x,y=map(int,input().split())
    home.append((x,y))
    
nCr = combinations(home, k)
answer=[]
for daepi in nCr: #대피소 지정
    result=0
    for other in home:
        if other not in daepi: #대피소가 아닌 집들
            min_d=math.inf
            for i in daepi: #대피소가 아닌 집들과 대피소인 집 거리 계산해서
                min_d=min(min_d,distance(i,other))
            result=max(min_d,result)
    answer.append(result)
print(min(answer))