BOJ 15686 치킨 배달

https://www.acmicpc.net/problem/15686
시간 1초, 메모리 512MB

input :

• N M(2 ≤ N ≤ 50)(1 ≤ M ≤ 13)
• 도시의 정보(1 <= 집의 개수 <= 2 * N)(M <= 치킨 집 <= 13)

output :

• 첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력

조건 :

• 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다.

• 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

• 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1 - r2| + |c1 - c2|

---

조건이 글로 나와 있어서 더 주의 해야 하는데 치킨 집의 개수는 끽 해봐야 13개다. 고를 수 있는 치킨 집은 M개인데 13개 중에 m을 고르는 모든 경우를 따져봐야 몇 개 안 된다. 그것도 그렇고 집도 개수가 100개보다 적다.

그냥 조합을 통해 모든 경우를 확인하던지 재귀를 통해 정해서 움직이던지 해야 한다.

import sys
from itertools import combinations

n, m = map(int, sys.stdin.readline().split())
home, chicken = [], []

for i in range(n):
    temp = list(map(int, sys.stdin.readline().split()))

    for j in range(n):
        if temp[j] == 1:
            home.append((i, j))
        elif temp[j] == 2:
            chicken.append((i, j))

temp, ans = list(combinations(chicken, m)), float('inf')
for i in range(len(temp)):
    survive = temp[i]
    temp_ans = [float('inf')] * len(home)

    for j in range(len(survive)):
        for k in range(len(home)):
            r1, c1 = survive[j][0], survive[j][1]
            r2, c2 = home[k][0], home[k][1]

            temp_ans[k] = min(temp_ans[k], abs(r1 - r2) + abs(c1 - c2))

    ans = min(sum(temp_ans), ans)

print(ans)