파이썬 | 백준 | 15686 | 치킨 배달 | 조합(combinations)

solution

1. 조합을 이용해 전체 치킨집에서 M개 선택

2. 집에서 치킨거리를 각각 구해 최소가 되는 조합을 구함

# 15686, 치킨 배달
import sys
from itertools import combinations

def getDistance(x, y):
    min_ = 100
    for i in range(len(y)):
        min_ = min(min_, abs(y[i][0]-x[0])+abs(y[i][1]-x[1]))
    return min_


N, M = map(int, sys.stdin.readline().split())
city = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

home = []
chicken = []

for i in range(N):
    for j in range(N):
        if city[i][j] == 1:
            home.append((i, j))
        elif city[i][j] == 2:
            chicken.append((i, j))

chicken_candidate = list(combinations(chicken, M))
chicken_distance = []

for i in range(len(chicken_candidate)):
    dis = 0
    for j in range(len(home)):
        dis += getDistance(home[j], chicken_candidate[i])
    if dis != 0:
        chicken_distance.append(dis)

print(min(chicken_distance))

29380KB

604ms

 

문제 출처 https://www.acmicpc.net/problem/15686

15686번: 치킨 배달