[백준] 16586번: 치킨 배달

문제

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

15686번: 치킨 배달

 

풀이

백트래킹을 사용해 풀었습니다.

home에 집 위치를, chicken에 치킨집 위치를 저장합니다.

DFS를 사용해 M개의 치킨집을 선택해 도시의 치킨 거리를 구합니다.

※ 치킨집은 많을수록 최소 거리에 유리합니다.

 

코드

파이썬

import sys

input = sys.stdin.readline
INF = sys.maxsize

N, M = map(int, input().split())
board = [list(input().split()) for _ in range(N)]

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

answer = INF
n = len(chicken)
stack = []
check = [False] * n


def DFS(start):
    global answer
    if len(stack) == M:
        total = 0
        for r1, c1 in home:
            dist = []
            for r2, c2 in stack:
                dist.append(abs(r1 - r2) + abs(c1 - c2))
            total += min(dist)
        answer = min(answer, total)
    else:
        for i in range(start, n):
            if not check[i]:
                check[i] = True
                stack.append(chicken[i])
                DFS(i + 1)
                stack.pop()
                check[i] = False


DFS(0)
print(answer)