백준 28215 대피소 파이썬

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

28215번: 대피소

문제에서 최대 K개의 대피소를 설치할 수 있고 거리가 최소가 될 때 최대값을 구하라고 했으니 백트레킹을 사용하면 모든 경우의 수를 탐색할 수 있어 문제를 풀 수 있을 것이라 생각했다.

 

그래서 처음에는 문제를 풀기위해 아래와 같이 코딩했었다.

import sys
def ch(w):#대피소의 개수에 따라 최솟값을 구하는 알고리즘
    global mins
    maxs = 0#최소거리의 최대값을 여기에 저장해 줄거임
    if len(w) ==1:#대피소가 1개 일때
        for i in range(n):
            if i not in w:
                x, y = s[i]
                maxs = max(maxs,(abs(s[w[0]][0] -x) + abs(s[w[0]][1]-y)))
                
        mins = min(mins,maxs)
    elif len(w)==2:#대피소가 2개 일때
        for i in range(n):
            if i not in w:
                x, y = s[i]
                w2 = min((abs(s[w[1]][0] -x) + abs(s[w[1]][1]-y)),(abs(s[w[0]][0] -x) + abs(s[w[0]][1]-y)))
                maxs = max(maxs,w2)
        mins = min(mins,maxs)
        
    elif len(w)==3:대피소가 3개 일때
        for i in range(n):
            if i not in w:
                x, y = s[i]
                w3 = min((abs(s[w[2]][0] -x) + abs(s[w[2]][1]-y)),(abs(s[w[1]][0] -x) + abs(s[w[1]][1]-y)),(abs(s[w[0]][0] -x) + abs(s[w[0]][1]-y)))
                maxs = max(maxs,w3)
        mins = min(mins,maxs)
 

def back(w,i):#백트레킹 코드
    if len(w) == k:
        ch(w)
        return
    for q in range(i,n):
        w.append(q)
        back(w,i)
        w.pop()


n,k = map(int,input().split())
s = []
mins = sys.maxsize#최대값을 저장해줌 
for _ in range(n):
    x,y = map(int,input().split())
    s.append([x,y])
back([],0)
print(mins)

너무 경우의 수를 나눠서 비효율적인 코딩이여서 아래와같이 최적화를 해줬다.

import sys
def ch(w):
    global mins, rkqt
    maxs = 0
    for i in range(n):
        if i not in w:
            save = []#리스트를 만들어 각 대피소 거리를 다 저장해줌
            x, y = s[i]
            for j in w:
                save.append((abs(s[j][0] -x) + abs(s[j][1]-y)))
            maxs = max(maxs,min(save))#최솟값으로 비교후 저장
    mins = min(mins,maxs)#
    
def back(w,i):
    if len(w) == k:
        ch(w)
        return
    for q in range(i,n):
        w.append(q)
        back(w,i)
        w.pop()


n,k = map(int,input().split())
s = []
mins = sys.maxsize
for _ in range(n):
    x,y = map(int,input().split())
    s.append([x,y])
back([],0)
print(mins)