백준 15686 치킨 배달

n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
chicken = []
home = []
for i in range(n):
    for j in range(n):
        if g[i][j] == 2:
            chicken.append((i, j))
        elif g[i][j] == 1:
            home.append((i, j))
l = len(chicken)
chickenzip = [[] for _ in range(2**l)]
k = 0
for i in range(1 << l):
    for j in range(l):
        if i & (1 << j):
            cx, cy = chicken[j]
            chickenzip[k].append((cx, cy))
    k += 1
ans = 50 * 50 * 2 * 50
for i in range(1, len(chickenzip)):
    if len(chickenzip[i]) > m:
        continue
    total = 0
    for hx, hy in home:
        min_dist = n * n
        for cx, cy in chickenzip[i]:
            min_dist = min(abs(hx-cx) + abs(hy-cy), min_dist)
        total += min_dist  
    ans = min(ans, total)
print(ans)

처음에 ans 의 초기값은 nnl로 잡았더니 너무 작았는지 틀려서 걍 크게 잡음
비트마스크로 모든 집합을 구해서 정답 구함
치킨집을 최대 m개라는 조건을 생각해야하는데 까먹고 있었음
비트마스크 아직 잘 몰라서 코드 짜는데 헤맴

n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
home = []
store = []
for i in range(n):
    for j in range(n):
        if g[i][j] == 1:
            home.append((i, j))
        elif g[i][j] == 2:
            store.append((i, j))
            
combination = []
print(list(combinations(store, )))
def go(index, l):
    if index == len(store):
        if len(l) <= m:
            combination.append(l)
            return
    else:
        go(index+1, l)
        go(index+1, l + [store[index]])
go(0, [])

def homedist(index, combination):
    chicken_dist = n * n + 1
    hx = home[index][0]
    hy = home[index][1]
    for i in range(len(combination)):
        cx = combination[i][0]
        cy = combination[i][1]
        chicken_dist = min(chicken_dist, abs(cx-hx)+abs(cy-hy))
    return chicken_dist

ans = n * n * (m+1)

for i in range(len(combination)):
    tmp_ans = 0
    for index in range(len(home)):
        tmp_ans += homedist(index, combination[i])
    #모든 집에서의 치킨 거리 구했으면 최솟값인지 확인    
    ans = min(tmp_ans, ans)

print(ans)

재귀를 이용한 조합 ..