[python] 15686번: 치킨 배달 풀이

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

15686번: 치킨 배달

분류

브루트포스 , 구현

구현 방향

모든 집에 대해, 모든 치킨집과의 거리 중 가장 짧은 치킨집과의 거리. "치킨 거리"를 구한다.
치킨집에서 M개를 택하는 모든 '조합'에 대해 치킨 거리를 계산하고 그 중 가장 작은 치킨 거리 총합을 구한다.

코드

from sys import stdin
from itertools import combinations


def dist(house, chicken):
    return abs(house[0] - chicken[0]) + abs(house[1] - chicken[1])


def dist_sum(house, chickens, case):
    dist_list = [10000] * len(house)
    i = 0
    distance = 0
    for loc in house: # 모든 집에 대해
        for chicken in chickens: # 가능한 모든 치킨집 중
            if chicken in case: # 이번 M개 치킨 조합에 속하는 치킨 집들에 대해
                distance = dist(loc, chicken) # 거리를 계산해서
                if dist_list[i] > distance: # 최소 거리 일 경우 기록한다.
                    dist_list[i] = distance
        i += 1

    return sum(dist_list) # 모든 집들의 치킨 거리의 합을 반환한다


N, M = map(int, stdin.readline().split())
chickens = []
house = []
board = []

for i in range(N):
    li = list(map(int, stdin.readline().split()))
    board.append(li)

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

cases = list(combinations(chickens, M))

dists = 1e9

for case in cases: # 가능한 M개 치킨집 조합에 대해서 
    dists = min(dists,dist_sum(house,chickens,case)) # 최소 치킨 거리 합을 찾는다.

print(dists)

치킨이 나오면 언제나 즐겁다.