[백준/Python] 15686 치킨 배달

문제 링크

15686번: 치킨 배달

 

문제 풀이

• k(>m)개 만큼의 치킨집이 있을 때, m개의 치킨을 선택하는 경우의 수는 kCm으로 구할 수 있고, 파이썬에서는 combinations를 사용해서 경우를 구할 수 있다. 
• 집에서 가장 가까운 치킨집의 거리를 더하고, 각 격우 중 제일 작은 값일 때가 최솟값이 된다.

 

전체 코드

import sys
from itertools import combinations

n, m = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

house = []
chicken = []
for i in range(n):
    for j in range(n):
        # 집 위치
        if arr[i][j] == 1:
            house.append([i, j])
        # 치킨 집 위치
        if arr[i][j] == 2:
            chicken.append([i, j])

result = 9999
for i in combinations(chicken, m): # m개의 치킨 집을 선택하는 모든 경우
    total = 0
    for k in house:
        chicken_len = 9999
        for j in i:
            chicken_len = min(chicken_len, abs(k[0]-j[0]) + abs(k[1]-j[1]))
        total += chicken_len
    result = min(result, total)

print(result)