[백준] 15686 - 치킨 배달 (python)

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

15686번: 치킨 배달

 

from itertools import combinations
t, num1 = map(int, input().split())
chick_x_y = []
home_x_y = []
for i in range(t):
    coordinate = list(map(int, input().split()))
    for j in range(len(coordinate)) :
        if coordinate[j] == 1 :
            home_x_y.append([j+1, i+1])
        if coordinate[j] == 2 :
            chick_x_y.append([j+1, i+1])
total = []
for i in range(len(chick_x_y)):
    s = []
    for j in range(len(home_x_y)):
        q = abs(chick_x_y[i][0] - home_x_y[j][0])
        t = abs(chick_x_y[i][1] - home_x_y[j][1])
        p = q+t
        s.append(p)
    total.append(s)
com = list(combinations(total, num1))
toa = []
for i in range(len(com)):
    to = []
    for j in range(len(com[0][0])):
        middle = []
        for p in range(num1):
            middle.append(com[i][p][j])
        to.append(min(middle))
    toa.append(to)
answer = []
for ui in range(len(toa)):
    answer.append(sum(toa[ui]))
print(min(answer))

 

풀이 : 각 치킨집, 집의 x, y 좌표를 저장한뒤 각 치킨집에 대하여 집에 대한 거리를 전부 구하여 치킨집에 대한 조합을 itertools 라이브러리를 이용해 구함.

 

각 조합에서의 최솟값만을 추출하여 전부 합을 구한뒤 그중에 최소값만을 출력 하였음.