이번에 해결해 볼 문제는 백준에 있는 치킨 배달이다.
문제 설명
- N x N 크기의 도시가 있다.
- 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다.
- 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리이다.
- 도시의 치킨 거리 : 모든 집의 치킨 거리의 합
- 도시에 있는 치킨집 중에서 M개의 치킨집을 고를 때 도시의 치킨 거리 최솟값을 출력하는 것이다.
문제 아이디어
- 1 <= M <= 13이고 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같으므로 combination을 직접 써도 해결이 가능하다.
- 최대 : 13C6 = 1716의 경우의 수
- 앞에서 정해진 치킨집을 가지고 도시의 치킨 거리를 구하면 된다.
문제 해결 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
chicken = [] # 치킨집이 있는 위치
house = [] # 집이 있는 위치
for i in range(n):
line = list(map(int, input().split()))
for j in range(n):
if line[j] == 1:
house.append([i, j])
elif line[j] == 2:
chicken.append([i, j])
from itertools import combinations
result = int(1e9)
for c in combinations(chicken, m):
val = 0 # 도시의 치킨 거리
for hx, hy in house:
house_val = 2*n # 치킨 거리
for cx, cy in c:
house_val = min(house_val, abs(cx-hx) + abs(cy-hy))
val += house_val
result = min(result, val)
print(result)