[백준] 15686번 치킨 배달, Python

문제 링크

1. 집과 치킨집의 위치정보를 모두 리스트에 넣는다.
2. 치킨집 개수에서 중복 없이 m개를 추출하는 모든 조합의 수를 구한다.
3. 모든 치킨집 조합에 대해 각 집과의 최소 거리를 구해 갱신하고, 이를 모두 더한 후 각 조합 별 최소 거리를 한 리스트에 담는다.
4. 최종 리스트에서 최솟값이 최소 치킨 거리가 된다.

import itertools
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
arr = []

for _ in range(n):
    arr.append(list(map(int, input().split())))

#집과 치킨의 위치정보 모두 리스트에 넣기
homearr = []  #집 위치정보
foodarr = []  #치킨 위치정보
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            homearr.append([i, j])
        elif arr[i][j] == 2:
            foodarr.append([i, j])
# print("homearr")
# print(homearr)
# print("foodarr")
# print(foodarr)
# 치킨집 중 중복 없이 m개를 추출
targetlist = list(itertools.combinations(foodarr, m))
# print("targetlist")
# print(targetlist)
#각 조합별 치킨거리 담을 배열
targetlistfar = []

if m == 1: # 치킨집이 1개만 필요하면 foodarr에서 하나만 뽑아서 검사하면 된다.
    targetlist = foodarr
    # print("targetlist")
    # print(targetlist)
    for i in range(len(targetlist)):
        #각 가정집과 해당 치킨집의 치킨거리 담을 배열
        homearrvisited = [10*9] * len(homearr)
        x1 = targetlist[i][0]
        y1 = targetlist[i][1]
        for j in range(len(homearr)):
            x2 = homearr[j][0]
            y2 = homearr[j][1]
            totallen = abs(x1 - x2) + abs(y1 - y2)
            if homearrvisited[j] > totallen:
                homearrvisited[j] = totallen
        #한팀 돌았으면 팀의 치킨거리 모두더함
        totalsum = sum(homearrvisited)
        targetlistfar.append(totalsum)
else:
    for i in range(len(targetlist)):
        #각 가정집과 해당 치킨집의 치킨거리 담을 배열
        homearrvisited = [10*9] * len(homearr)
        for j in range(len(targetlist[i])):
            x1 = targetlist[i][j][0]
            y1 = targetlist[i][j][1]
            # print("(", x1, ",", y1, ")")
            for k in range(len(homearr)):
                x2 = homearr[k][0]
                y2 = homearr[k][1]
                # print("(", x2, ",", y2, ")")
                totallen = abs(x1 - x2) + abs(y1 - y2)
                if homearrvisited[k] > totallen:
                    homearrvisited[k] = totallen
        #한팀 돌았으면 팀의 치킨거리 모두더함
        totalsum = sum(homearrvisited)
        targetlistfar.append(totalsum)

print(min(targetlistfar))