백준 15686치킨배달

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

15686번: 치킨 배달

처음에 bfs를생각했는데 더 간단한 풀이가 있었다.

 

모든 집과 치킨집을 구해놓고,

치킨집에 대한 원소가m개인 combination을 구하고,

각 combination에 대하여 치킨 거리를 구해 비교한다.

import sys

from itertools import combinations

input=sys.stdin.readline




n,m=map(int,input().split())
arr=[]
chickenhouse=[]
blank=[]
for i in range(n):
    tmp=list(map(int,input().split()))
    for j in range(n):

        if tmp[j]==1:
            blank.append((i,j))

        elif tmp[j]==2:
            chickenhouse.append((i,j))

chicken_comb=combinations(chickenhouse,m)
answer=1e+7
for chickens in chicken_comb:
    dist=0
    for i,j in blank:
        dist+=min([abs(i-c[0])+abs(j-c[1]) for c in chickens])
        if dist>=answer:break
    answer=min(answer,dist)
print(answer)