백준 15686 치킨 배달

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

 

 치킨거리란 집과 가장 가까운 치킨집 사이의 거리이다. 그리고 도시의 치킨거리란 모든 집의 치킨거리를 합한 것이다. 우리가 주어진 치킨집 중 M개의 치킨집만을 남겨야 할 때, 도시의 치킨거리가 최소가 되게하는 경우의 도시의 치킨거리를 출력하는 문제이다. 이 때 0은 빈곳, 1은 집, 2는 치킨 집으로 인풋이 주어진다.

 

 이 문제는 딱 봐도 복잡한 형식이다. 그렇기에 사실 마땅한 알고리즘보단 하나하나 차분히 나누어 충실히 구현하여 문제를 풀어야한다. 먼저 우리는 집과 치킨집 사이의 치킨거리를 구해서 2d 배열로 저장해놓을 필요가 있다. 그래야 치킨집을 하나씩 없애보며 도시의 치킨거리를 구할 수 있다. 그리고 M개가 될 때까지 치킨집들을 없애보고, 이 경우를 모든 경우를 구해보고, 개 중 최소를 구한다. 단순히 구현하고, 다 해보고, 백트랙킹 하여 구하는 것이다.

 

import sys
input = sys.stdin.readline
import math

def back(now,mins,visited):
    global min_
    if len(visited)==M:
        min_=min(sum(mins),min_)
        return
    
    for i in range(len(chicken)):
        if i>now and i not in visited:#중첩 방지
            visited.append(i)
            back(i,[min(a,b) for a,b in zip(mins,c_distance[i])],visited)
            #그때마다 최소갱신
            visited.pop()


N,M = map(int,input().rstrip().split())

house=[]
chicken=[]

for a in range(N):
    line=list(map(int,input().rstrip().split()))
    for b,cell in enumerate(line):
        if cell == 1:
            house.append([a,b])
        elif cell == 2:
            chicken.append([a,b])

c_distance = [[0 for x in range(len(house))] for y in range(len(chicken))]
#치킨거리 저장

for a in range(len(chicken)):
    for b in range(len(house)):
        c_distance[a][b] = abs(house[b][0]-chicken[a][0])+abs(house[b][1]-chicken[a][1])

min_=math.inf
back(-1,[math.inf]*len(house),[])
print(min_)