[백준] 15686 치킨거리 in Python

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

15686번: 치킨 배달

유형 : 구현 , 완전 탐색

 

1. 치킨집들 중에서 m개의 치킨집을 고르는 모든 경우를 구하기 위해서 combinations() 함수를 사용한다 

2. m개의 치킨집 고르는 경우의 도시치킨거리를 구하기 위한 함수 check_sum을 정의한다.

home에 저장한 모든 집의 좌표를 확인하면서 각각의 집에서 가장 가까운 치킨집과의 거리를 구하여 모두 더해준다.

# 치킨 배달
from itertools import combinations

n, m = map(int, input().split())

home = []
chicken = []

for i in range(n):
    array = list(map(int, input().split()))
    for j in range(n):
        if array[j] == 1:
            home.append((i, j))
        if array[j] == 2:
            chicken.append((i, j))

candidates = list(combinations(chicken, m)) # m 개의 치킨집을 뽑는 연산

def get_sum(candidates):
    result = 0
    for hx, hy in home:
        temp = 1e9
        for cx, cy in candidates:
            temp = min(temp, abs(hx- cx) + abs(hy - cy))
        result += temp
    return result

result = 1e9
for candi in candidates:
    result = min(result, get_sum(candi))
print(result)