백준 15686) 치킨배달 (골드.5)

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

15686번: 치킨 배달

문제는 조건에 맞는 모든 경우의 수를 확인하고 최적의 값을 찾아내는 완전탐색 및 백트래킹 문제이다. 문제의 조건은 다음과 같다. 

1) 가게(r1, c1)와 집(r2, c2)과의 거리는 |r1-r2| + |c1-c2|이다. 

2) 최대 m개의 치킨 가게를 둘 수 있다. 

3) 각각의 집에서 치킨 가게의 거리의 합이 가장 작을 때의 값을 구하라. 

 

최대 m개의 치킨 가게를 둘 수 있을 때 모든 치킨-집의 거리가 작을 수 있을 때에는 m개의 치킨 가게가 있을 때이다. 

따라서 m개의 치킨가게가 promising 조건이 될 수 있다. 

조건에 맞는 경우의 수를 모두 탐색하기 위해서 dfs를 사용하였다. 

 

여기서 탐색할때 계속해서 시간초과가 발생했는데 알고보니 dfs의 for문에서 index 대신 depth를 사용해서 문제가 발생한 거였다 🤦‍♀️

작은 오타라도 주의하자 !!

from math import inf
import sys 

global answer, n, m, house, chicken, q
n, m = map(int, sys.stdin.readline().split())
chicken = []
house = []
answer = inf
q = []

for i in range(n):
    line = list(map(int, sys.stdin.readline().split()))
    for j in range(n):
        if line[j] == 1 : 
            house.append((i, j))
        elif line[j] == 2 :
            chicken.append((i, j))

def calculateDistance(h, chicken) :
    distance = inf
    for c in chicken : 
        distance = min(distance, abs(h[0]-c[0]) + abs(h[1] - c[1]))
    return distance

def calculateTotalDistance(house, chicken) :
    total = 0 
    for h in house : 
        total += calculateDistance(h, chicken)
    return total 

def dfs(depth, index) :
    global answer, n, m, house, chicken, q
    if depth == m : 
        answer = min(answer, calculateTotalDistance(house, q))
        return 
    for i in range(index, len(chicken)) :
        q.append(chicken[i])
        dfs(depth + 1, i + 1)
        q.pop()


if len(chicken) == m : 
    print(calculateTotalDistance(house, chicken))
else : 
    dfs(0, 0)
    print(answer)