[백준/Python] 15686번 : 치킨 배달

문제

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

15686번: 치킨 배달

---

풀이

입력받은 도시의 정보에서 치킨집과 집의 위치를 찾아 리스트에 저장한다.
itertools의 combinations함수를 이용하여 전체 치킨집 중 m개의 치킨집을 선택한 조합을 comb에 저장한다.
각 집마다 m개의 치킨집 중 치킨 거리가 가장 작은 값을 dist에 더해준다.
모든 집을 확인한 후 새로운 리스트에 dist를 넣어준다. (dist = 도시의 치킨 거리)
comb를 모두 확인하면 새로운 리스트에서 최솟값을 출력한다.

---

코드

import sys
input = sys.stdin.readline
from itertools import combinations
n, m = map(int, input().split())
board = [[*map(int, input().split())] for _ in range(n)]

shop, home = [], []
for i in range(n):
    for j in range(n):
        if board[i][j] == 2:
            shop.append((i, j))
        if board[i][j] == 1:
            home.append((i, j))

all = []
comb = combinations(shop, m)
for s in comb:
    dist = 0
    for i in home:
        min_d = 101
        for j in s:
            min_d = min(min_d, abs(i[0] - j[0]) + abs(i[1] - j[1]))
        dist += min_d
    all.append(dist)

print(min(all))