치킨 배달 [백준 15686번]

문제

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

15686번: 치킨 배달

 

내 풀이

 

나도 combinations 써서 구현할까 하다가 재귀 함수 연습할 겸 재귀로 풀어보았다.

 

재귀 함수 백트래킹을 사용하여 치킨집 중에서 M개를 선택하였다.

선택된 치킨집과 집과의 거리를 구하였다.

 

import sys, math
input = sys.stdin.readline

N, M = map(int, input().strip().split())
city, house, chick = [], [], []
for i in range(N):
    city.append(list(map(int, input().strip().split())))
    for j in range(N):
        if city[i][j] == 1:
            house.append((i, j))
        elif city[i][j] == 2:
            chick.append((i, j))

MIN = math.inf
check = [False]*len(chick)
def dfs(arr):
    global MIN
    if len(arr) == M:
        dist = 0
        for h in house:
            md = math.inf
            for idx in arr:
                d = abs(h[0]-chick[idx][0]) + abs(h[1]-chick[idx][1])
                md = min(md, d)
            dist += md
        MIN = min(MIN, dist)        
        return
    for i in range(len(chick)):
        if not check[i] and (not arr or arr[-1] < i):
            check[i] = True
            arr.append(i)
            dfs(arr)
            arr.pop()
            check[i] = False
dfs([])
print(MIN)

 

총평

빡구현이다. 삼성 문제 치고 풀만하다.