[백준] 15686 파이썬(python) : 치킨 배달

15686번 : 치킨 배달

 

 

전체 치킨집에서 폐점시키지 않고 남겨둘 m개의 치킨집을 뽑는다.(이때 순서는 상관없으므로 순열이 아닌 조합이 된다.)

각 집을 기준으로 거리가 가장 가까운 치킨집을 구한다.(치킨거리)

그리고 치킨거리를 모두 더하면 도시의 치킨거리가 된다.

도시의 치킨거리 중 가장 작은 값을 출력!

 

조합을 이용한 풀이)

import sys
from itertools import combinations
n, m = map(int, sys.stdin.readline().split())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
res = sys.maxsize
house, chicken = [], []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            house.append([i, j])
        elif graph[i][j] == 2:
            chicken.append([i, j])
for chi in combinations(chicken, m): #1
    city_len = 0 #2
    for h in house: #3
        chi_len = sys.maxsize #4
        for i in range(m): #5
            chi_len = min(chi_len, abs(h[0]-chi[i][0]) + abs(h[1]-chi[i][1])) #6
        city_len += chi_len #7
    res = min(res, city_len) #8
print(res)

 

#1 : 치킨집의 위치를 담은 리스트 chicken에서 m개의 치킨집을 순서에 상관없이 뽑는다

#2 : 도시의 치킨거리를 의미하는 변수

#3 : 집의 위치를 담은 리스트에서 위치 리스트를 하나씩 반복

#4 : 집에서 가장 가까운 치킨집의 거리인 치킨거리를 저장할 변수

#5 : m개의 치킨집을 꺼냈으니까 m번 반복

#6 : 문제에서 주어진 치킨거리를 구하는 식 구현

#7 : 치킨거리의 누적합인 도시의 치킨거리

#8 : 도시의 치킨거리 중 가장 작은값을 저장 후 출력