백준 15686 치킨 배달 (파이썬)

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

15686번: 치킨 배달

1. 집과 치킨집의 좌표를 home, chicken에 저장한다

2. 1부터 m까지 치킨집을 dfs로 구현한 조합으로 선택한다

3. 집으로부터 선택한 치킨집의 거리 중 최소값을 dist에 저장한다

4. dist의 합은 현재 선택한 치킨집의 치킨 거리이다. 따라서 dist 중 최소값을 출력

import sys

input = sys.stdin.readline

def length(dist):
    for i in range(len(home)):
        h_x, h_y = home[i]
        for j in range(len(c)):
            if c[j]:
                c_x, c_y = chicken[j]
                d = abs(h_x - c_x) + abs(h_y - c_y)
                dist[i] = min(d, dist[i])
    return sum(dist)

def comb(idx, cnt, r):
    global ans
    if cnt == r:
        dist = [sys.maxsize for _ in range(len(home))]
        ans = min(length(dist), ans)
        return

    for i in range(idx, len(chicken)):
        if c[i]:
            continue
        c[i] = 1
        comb(i + 1, cnt + 1, r)
        c[i] = 0

n, m = map(int, input().split())
a, chicken, home = [], [], []
for i in range(n):
    row = list(map(int, input().split()))
    a.append(row)
    for j in range(n):
        if a[i][j] == 1:
            home.append([i, j])
        if a[i][j] == 2:
            chicken.append([i, j])

c = [0 for _ in range(len(chicken))]
ans = sys.maxsize
for r in range(m):
    comb(0, 0, r+1)
print(ans)