치킨 배달

• 치킨집의 갯수가 최대 13이다. 그래서 그중에서 M개의 치킨집을 골라내는 모든 조합의 갯수는 최대 C(13,6) = 1716으로 매우 작으므로, 일일히 다 따져봐도 무리가 없다,
  • 최대 M개의 치킨집을 남길 수 있을때, M보다 작은 갯수의 치킨집을 남기는 것은 고려할 필요가 없다. 치킨집을 줄여서 치킨거리가 감소되는 것은 불가능하다
• M개의 치킨집의 목록이 주어졌을때, 각 집의 치킨 거리를 구하는 것은 O(M)이고, H개의 집을 포함하는 도시의 치킨 거리를 구하는 것은 O(MN)이다.
• 따라서 총 시간복잡도는 처음 데이터를 읽어들이는데에 걸리는 O(N*N)과 모든 조합에 대해서 치킨거리를 계산하는 O(C(K,M)*M*H)이다 (K는 치킨집의 총 갯수, H은 집의 총 갯수) 을 합친 O(N^2 + C(K,M)*M*H) 가 되고 H=O(N)이므로 O(N^2 + C(K,M)*M*N)가 된다.
• 각 치킨집과 집과의 거리들을 미리 구해서 테이블에 저장해놓으면 약간의 속도 향상을 얻을수 있다.

"""Solution code for "BOJ 15686. 치킨 배달".

- Problem link: https://www.acmicpc.net/problem/15686
- Solution link: http://www.teferi.net/ps/problems/boj/15686
"""

import itertools

INF = float('inf')


def main():
    N, M = [int(x) for x in input().split()]
    all_chickens, houses = [], []
    for r in range(N):
        line = input()
        for c, info in enumerate(line.split()):
            if info == '1':
                houses.append((r, c))
            elif info == '2':
                all_chickens.append((r, c))

    dists = []  # dists[i][j] = dist from i-th house to j-th chicken store.
    for hr, hc in houses:
        dists.append([abs(hr - cr) + abs(hc - cc) for cr, cc in all_chickens])

    min_dist = INF
    for chickens in itertools.combinations(range(len(all_chickens)), M):
        dist = 0
        for dists_from_house in dists:
            dist += min(dists_from_house[x] for x in chickens)
        min_dist = min(min_dist, dist)

    print(min_dist)


if __name__ == '__main__':
    main()