Home [백준] 15686번 치킨 배달 - Python
Post
Cancel

[백준] 15686번 치킨 배달 - Python

이번에 해결해 볼 문제는 백준에 있는 치킨 배달이다.


문제 설명

  1. N x N 크기의 도시가 있다.
  2. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다.
  3. 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리이다.
  4. 도시의 치킨 거리 : 모든 집의 치킨 거리의 합
  5. 도시에 있는 치킨집 중에서 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)
This post is licensed under CC BY 4.0 by the author.

[백준] 14502번 연구소 - Python

[백준] 18352번 특정 거리의 도시 찾기 - Python