[백준][Python] 15686번 치킨 배달

15686번: 치킨 배달

 

코드

from itertools import combinations
n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
chicken = []
house = []
for i in range(n):
   for j in range(n):
      if graph[i][j] == 2:
         chicken.append((i,j))
      elif graph[i][j] == 1:
         house.append((i,j))

length = int(1e9)
for comb in combinations(chicken,m):
	l = 0
	for i,j in house:
		h = int(1e9)
		for a,b in comb:
			h = min(h,abs(i-a)+abs(j-b))
		l += h
	length = min(length,l)

print(length)

 

설명

 

우선 chicken과 house에 치킨집과 집의 위치를 저장한다.

 

combinations를 활용하여 n개를 고를 수 있는 모든 조합을 고려한다. 

n개의 치킨집 중에서 현재 집과 가장 가까운 거리에 있는 치킨집을 골라 그 거리를 총 거리(l)에 더해준다.

 

모든 집에 대한 거리를 구했으면 총 거리의 최솟값인 length 값을 갱신시킨다.