[알고리즘] 치킨배달 - 백트래킹

문제

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

15686번: 치킨 배달

풀이 팁

1. m개의 치킨집이 선택되어 나올 수 있는 "모든 경우의 수를 찾는 문제"

- 모든 경우의 수는 : " 조합 or 백트래킹 " 이렇게 접근가능 하다고 생각한다

- 조합의 경우는 시간복잡도가 높게 나오기에 코테에서 못쓴다고 봐도 무방하다

- 그러므로 백트래킹으로 접근하는걸 추천한다

 

2. chicken집의 개수가 m개이상이므로 idx, cnt 2가지의 parameter를 둔다

- 왜냐하면 idx가 증가함에 따라 특정 치킨집은 선택될 수 있지만, 안될수도 있기 때문에 choose()를 아래의 코드와 같은 식으로 재귀적으로 호출해주자

 

코드

import sys

n,m = map(int,input().split())
arr = [
    list(map(int,input().split()))
    for _ in range(n)
]

ans, home, chicken = list(), list(), list()
min_dist = sys.maxsize

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

def calc():
    dist = 0
    for x,y in home:
        tmp = sys.maxsize
        for idx in ans:
            i,j = chicken[idx]
            tmp = min(tmp, abs(x-i) + abs(y-j))
        dist += tmp
    return dist

def choose(idx, cnt):
    global min_dist

    if idx > len(chicken):
        return
    
    if cnt == m:
        min_dist = min(min_dist, calc())
        return
    
    ans.append(idx)
    choose(idx+1, cnt+1)
    ans.pop()
    choose(idx+1, cnt)

choose(0,0)
print(min_dist)