[Python] 치킨 배달 - 백준

해당 글은 백준 15686번 문제 '치킨 배달'을 다룬다.

문제

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

15686번: 치킨 배달

 

설명

조합 라이브러리와 3중 for문으로 해결할 수 있는 문제..!

문제만 읽었을 땐, 쉬워보였는데 의외로 오래 걸렸당..

치킨집이 아니라 집을 기준으로 조합으로 얻은 m개의 치킨집의 거리를 구해야 하는데 핵심이다!

 

코드

from itertools import combinations

n, m = map(int, input().split())
house = []
chicken = []
for i in range(n):
    arr = list(map(int, input().split()))
    for j in range(n):
        r, c = i+1, j+1
        if arr[j] == 1:
            house.append((r, c))
        elif arr[j] == 2:
            chicken.append((r, c))

result = []
for combi in combinations(chicken, m):
    temp = []
    for i in range(len(house)):
        dist = 1e9
        for j in range(len(combi)):
            dist = min(dist, abs(combi[j][0]-house[i][0])+abs(combi[j][1]-house[i][1]))
        temp.append(dist)
    result.append(sum(temp))
print(min(result))