[백준/파이썬] 15686번 치킨 배달

solved.ac Class 4레벨에 속한 문제이다.

문제 주소: https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

문제 해석

1은 집, 2는 치킨집을 나타낸다.

 

치킨 거리는 집으로 부터 가장 가까운 치킨집 사이의 거리이며,

모든 집으로 부터 치킨 거리의 합이 도시의 치킨 거리가 된다.

 

m개의 치킨집만 선택해 도시에 남겨야 한다.

이때 도시의 치킨 거리가 최소가 되는 값을 구하는 문제이다.

문제 풀이

먼저 집과 치킨집의 좌표를 따로 저장해주었다.

이후 dists 리스트에 치킨집으로 부터 거리를 미리 모두 구해주었다.

 

m개의 치킨집을 dfs를 통해 선택해주었다.

 

m개가 선택되면 해당 치킨집이 존재할 경우 치킨 거리를 구해주며 갱신해주면 된다.

문제 코드

import sys
input = sys.stdin.readline

def cal_dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def solve(n, m, homes, chickens):
    answer = float('inf')
    dists = []
	# 각 치킨집으로 부터 치킨 거리를 모두 구해놓기
    for i in range(len(chickens)):
        temp = []
        for j in range(len(homes)):
            temp.append(cal_dist(chickens[i], homes[j]))
        dists.append(temp)

    def dfs(depth, selects, k):
        nonlocal answer

        if depth == m:
            # 선택한 치킨집들의 최소 치킨거리 구하기
            temp = [float('inf')] * len(homes)
            for i in selects:
                for j in range(len(homes)):
                    temp[j] = min(temp[j], dists[i][j])
            # 갱신
            answer = min(answer, sum(temp))
            return

        for i in range(k, len(chickens)):
            selects.append(i)
            dfs(depth + 1, selects, i + 1)
            selects.pop()
        return
    dfs(0, [], 0)
    return answer

# input
n, m = map(int, input().split())
chickens = []
homes = []
for i in range(n):
    temp = list(map(int, input().split()))
    for j in range(n):
        if temp[j] == 1:
            homes.append((i, j))
        elif temp[j] == 2:
            chickens.append((i, j))
print(solve(n, m, homes, chickens))

제출 결과