BOJ 15686 - 치킨 배달

풀이

---

주어진 크기의 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)

References

---

• BOJ 15686 - 치킨 배달