[Baekjoon/Python] 15686번: 치킨 배달(BackTracking)

# Baekjoon 15686번: 치킨 배달
import sys
from collections import deque
from itertools import combinations
input = sys.stdin.readline

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

city = [[] for _ in range(N)]
market_info = []
house_info = []
tlst = []

for i in range(N):
    arr = input().split()
    for j in range(N):
        city[i].append(int(arr[j]))
        if arr[j] == '2':
            market_info.append((i, j))
        elif arr[j] == '1':
            house_info.append((i, j))

def cal(temp): # 최단 거리 계산 함수
    ans = 0
    for h_y, h_x in house_info:
        limit = float('inf')
        for m_y, m_x in temp:
            distance = abs(m_y-h_y) + abs(m_x-h_x)
            limit = min(limit, distance)
        
        ans += limit

    return ans

res = float('inf')

def dfs(tlst, m):
    global M, res

    if m == len(market_info): # 모든 가게를 고려한 경우
        if len(tlst) == M: # M개의 가게를 선정한 경우
            res = min(res, cal(tlst))
        return 
    
    dfs(tlst + [market_info[m]], m+1) # 가게 유지
    dfs(tlst, m+1) # 가게 폐업

dfs(tlst, 0)
print(res)

이 문제는 백트래킹(Backtracking) 알고리즘 문제이다. 백트래킹은 모든 경우의 수를 하나의 트리처럼 구성할 수 있고, 그 트리의 모든 가능성을 시도한다는 점이 특징이다. 탐색으로는 DFS를 사용하며, 탐색 중에 틀린 답이 있을 경우에는 이전 분기점으로 돌아간다. 보통 재귀 함수로 구현되며, DFS의 마지막 분기점에 도달했을 경우 return하는 형식이다.
먼저, 문제에서 입력한 치킨과 집의 좌표를 tuple 형태로 list에 저장해놓는다.(빠른 최단거리 계산을 위해서) DFS 내부에서는 모든 치킨집을 탐색하고, M개에 해당하는 치킨집을 선정했을 경우에만 cal 함수로 최단거리를 계산하도록 한다.


항상 재귀함수를 구현해야 할 때는 좀 더 생각을 많이해보자. 더 간단하게 답이 나올 수 있다.