[Python] 15686. 치킨 배달

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

15686번: 치킨 배달

---

순열로 완전탐색하여 도시 치킨거리를 구한다.

def next_perm(a):
    i = len(a)-1
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a)-1
    while a[i-1] >= a[j]:
        j -= 1
    a[i-1], a[j] = a[j], a[i-1]
    j = len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    return True

N, M = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(N)]

house = []
chicken = []

for y in range(N):
    for x in range(N):
        if MAP[y][x] == 1:
            house.append((y,x))
        elif MAP[y][x] == 2:
            chicken.append((y,x))

opt = [0]*(len(chicken)-M) + [1]*M
answer = 10**10

while True:
    candidate = []
    for i in range(len(chicken)):
        if opt[i] == 1:
            candidate.append(chicken[i])
    total_dist = 0
    for h in house:
        dist = []
        for c in candidate:
            dist.append(abs(h[0]-c[0])+abs(h[1]-c[1]))
        total_dist += min(dist)
    answer = min(total_dist, answer)

    if not next_perm(opt):
        break

print(answer)

 

문제를 푸는데 도움이 된 테스트 케이스