[python] 백준 15686 치킨 배달

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

15686번: 치킨 배달

 

문제 해결

• 치킨집을 m개로 줄여서 각 집에서 치킨집까지 최소거리 합을 구해야한다.
• 치킨집을 m개로 줄이는 경우의 수는 combinations 라이브러리를 이용하면 좋을 것이다.
• 그러기 위해서는 치킨집 좌표를 알아야할 것이다. for문을 통해 치킨집 좌표와 집 좌표를 구해놓자.
• 치킨집 m개를 뽑은 다음 집 하나 치킨집 하나씩 매칭 시켜가며 최소거리 합을 구해본다.
• 시간복잡도가 상당할 것 같지만 n,m이 모두 작다. 즉 백트래킹을 해도 괜찮다는 것이다.

 

CODE

from itertools import combinations
import sys
INF = sys.maxsize
ans = INF

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
chicken = []
house = []

for i in range(n):
    for j in range(n):
        if board[i][j] == 2:
            chicken.append((i,j))
        elif board[i][j] == 1:
            house.append((i,j))

for choice in combinations(chicken,m):
    temp = 0
    for h in house:
        d = sys.maxsize
        for one_choice in choice:
            d = min(d, abs(h[0]-one_choice[0])+abs(h[1]-one_choice[1]))
        temp += d
    ans = min(ans,temp)
print(ans)