[Python] 15686 치킨 배달

1. 문제 📚

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

15686번: 치킨 배달

2. 입출력 예 📋

3. 알고리즘 ✅

1. dfs를 이용하여 M개의 치킨 집 고르기

 

2. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다.

-> 각각의 집과 오픈한 치킨 집 중에서 가장 가까운 치킨집 거리를 구하기

 

3. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

-> for 문을 돌아가며 치킨 거리의 합을 구하기

 

 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구해야하기 때문에

4. 도시의 치킨거리를 확인하며 최솟값으로 바꿔주기

4. 소스코드 💻

import sys

input = sys.stdin.readline

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

chicken = []
home = []

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

open_chicken = []
visited = [False for _ in range(len(chicken))]

answer = 1e9

def cal(home, chicken):
    print(chicken)
    return abs(home[0] - chicken[0]) + abs(home[1] - chicken[1])

def dfs(start):
    global answer
    if M == len(open_chicken):
        city_chicken_dis = 0
        for i in range(len(home)):
            chicken_distance = 1e9
            for j in range(len(open_chicken)):
                # 치킨 거리
                chicken_distance = min(cal(home[i], open_chicken[j]), chicken_distance)
            # 도시 치킨 거리
            city_chicken_dis += chicken_distance

        answer = min(answer, city_chicken_dis)
        return

    for i in range(start, len(chicken)):
        if not visited[i]:
            visited[i] = True
            open_chicken.append(chicken[i])
            dfs(i)
            open_chicken.pop()
            visited[i] = False

dfs(0)
print(answer)