[백준] 15686번 치킨 배달 _ python

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

어떤 치킨집을 골라야 도시 치킨 거리가 최소가 될지 모르니까 전체 탐색으로 풀었다.
itertools의 combination을 썼는데 다른 분들 풀이를 보니 이 메소드를 활용한 더 짧고 간략한 풀이가 있다.

1차 시도 (성공)

import sys
from itertools import combinations

n, m = map(int, sys.stdin.readline().split())
town = []
for i in range(n):
    town.append(list(map(int, sys.stdin.readline().split())))

all_chicken = []
for j in range(n):
    for k in range(n):
        if town[j][k] == 2:
            all_chicken.append((j,k))

comb_chicken = list(combinations(all_chicken, m))

town_result = 10000
for comb in comb_chicken:
    dist = 0
    for x in range(n):
        for y in range(n):
            now_min = 10000
            if town[x][y] != 1:
                continue
            else:
                for num in range(m):
                    now = abs(comb[num][0]-x) + abs(comb[num][1]-y)
                    now_min = min(now_min, now)
            dist += now_min
    town_result = min(town_result, dist)

print(town_result)

다른 풀이

import sys
from itertools import combinations

input = sys.stdin.readline

n, m = map(int, input().split())
city = list(list(map(int, input().split())) for _ in range(n))
result = 999999
house = []      # 집의 좌표
chick = []      # 치킨집의 좌표

for i in range(n):	# 집과 치킨집의 좌표를 미리 구함
    for j in range(n):
        if city[i][j] == 1:
            house.append([i, j])
        elif city[i][j] == 2:
            chick.append([i, j])

for chi in combinations(chick, m):  # m개의 치킨집 선택 (조합)
    temp = 0            # 현재 조합에서 도시의 치킨 거리
    for h in house: 
        chi_len = 999   # 각 집마다 치킨 거리
        for j in range(m):
            chi_len = min(chi_len, abs(h[0] - chi[j][0]) + abs(h[1] - chi[j][1]))	
        temp += chi_len
    result = min(result, temp)	# 지금까지 조합 중 가장 짧은 도시의 치킨 거리를 저장

print(result)