Python 15686번 치킨 배달

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

 

문제에서는 최대 m개의 치킨집이 있을 경우 치킨 거리의 최소합을 구하라고 했다.

먼저 치킨집이랑 사람집을 따로 리스트를 만들어서 보관했고 그 이후 dfs 방식을 이용해서 문제에 접근했다.

cnt 즉 고른 치킨집의 개수가 최대 치킨집의 개수와 일치하면 계산을 시작했고 계산한 결과값을 result라는 리스트에 넣어줬다.

(처음에 result에 5001이라는 값을 넣어준 이유는 아래 resMin 처음 실행될때 빈 리스트일 경우 에러가 날 수도 있기 때문에 100*100을 확실하게 넣어주는게 맞긴 한데 최대가 5001을 초과할 일이 없어서 잘됐네요 ㅎ,,)

처음에 m개의 치킨집 개수를 loc라는 list에 append나 pop을 이용하려 했는데 여러 개를 넣고 빼다 보니 연산이 오래걸려서 index 방식으로 바꾸게 되었다.

돌려보니 index 방식은 제한 시간안에 통과했다!!!

import sys

input = sys.stdin.readline

n,m = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
chick=[]
result=[5001]
house = []
for i in range(n):
    for j in range(n):
        if ary[i][j]==2:
            chick.append([i,j])
        elif ary[i][j]==1:
            house.append([i,j])
def dfs(idx,cnt,loc):
    if cnt == m:
        calc(loc)
        return
    for i in range(idx,len(chick)):
        if not loc[i]:
            loc[i]=1
            dfs(i,cnt+1,loc)
            loc[i]=0
def calc(loc):
    sum = 0
    resMin = min(result)
    for i,j in house:
        value = 101
        for k in range(len(chick)):
            if loc[k]:
                x,y=chick[k]
                value = min(value,abs(i-x)+abs(j-y))
        sum+=value
        if sum > resMin:
            return
    result.append(sum)

dfs(0,0,[0 for _ in range(len(chick))])
print(min(result))