풀이
주어진 크기의 NxN 도시에서 치킨집을 M개만큼만 남겼을 때 집마다 최소거리를 줄 수 있는 조합을 찾는 문제다.itertools 의 combinations 모듈을 활용해 주어진 치킨집 조합을 찾고 각 조합마다 각 집들의 최소거리를 다 합해서 그 중 제일 적은 거리를 찾아내야한다.
예를 들어 1, 2, 3번 치킨집이 있고 M 이 2일 경우.(1, 2), (1, 3), (2, 3) 총 3가지 조합이 생기는데집마다 1번과 2번 치킨집 중 가까운 거리를 comb_min 에 더해준다.모든집들에 대한 반복이 끝나면 1번째 조합에 대한 치킨거리 즉 ans 가 나온다.
이 작업을 각 조합마다 반복해서 최소거리를 찾아내 출력하면된다.
소스코드
from itertools import combinations
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
town = []
house = []
chicken = []
for i in range(N):
t = list(map(int, input().split()))
town.append(t)
for j in range(N):
if t[j] == 1:
house.append((i, j))
elif t[j] == 2:
chicken.append((i, j))
comb = combinations(chicken, M)
ans = float("inf")
for c in comb: # 가능한 치킨집 경우의 수
comb_min = 0
for i, j in house:
min_dis = float("inf")
for x, y in c:
chi_dis = abs(x-i) + abs(y-j) # 각 치킨집과 집간의 치킨거리
min_dis = min(chi_dis, min_dis) # 경우의 수에서 최소 치킨거리
comb_min += min_dis # 경우의 수에서 모든 집간의 치킨거리
ans = min(ans, comb_min) # 최소 치킨거리를 갖는 조합
print(ans)