[BOJ 15686] 치킨 배달(Python)

---

문제

치킨 배달

---

문제 해설

브루트포스를 이용하여 도시의 치킨 거리의 최솟값을 구하는 문제입니다.

먼저, 치킨 거리의 최솟값을 구하는 문제이므로 치킨집을 M개로 고정시킵니다. 왜냐하면 치킨집을 M개 고르는 것이 반드시 최솟값을 가지게 되기 때문입니다.

다음은 치킨집과 일반집의 좌표를 리스트에 담습니다. 치킨집을 무작위로 M개 고르고 그때의 치킨거리를 구해야하기 때문에 치킨집과 일반집의 좌표가 필요합니다.

마지막으로 무작위 치킨집 M개를 고르고 그때의 치킨거리를 구합니다. 이렇게하면 모든 경우의 도시 치킨 거리를 구할 수 있습니다.

---

풀이 코드

from itertools import combinations
import sys

input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
chickens = []
houses = []
answer = sys.maxsize
# 그래프에서 치킨집이랑 일반집 찾기.
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            houses.append((i, j))
        elif graph[i][j] == 2:
            chickens.append((i, j))
# 무작위 치킨집을 m개 고르고 도시의 치킨거리를 갱신
for chicken in combinations(chickens, m):
    tot_dist = 0  # 무작위 치킨집 m개 중 도시의 치킨거리
    for house_x, house_y in houses:
        dist = sys.maxsize  # 무작위 치킨집 m개 중 각 집의 치킨거리
        for chicken_x, chicken_y in chicken:
            # 가장 가까운 치킨집 채택
            dist = min(dist, abs((chicken_x - house_x)) + abs((chicken_y - house_y)))
        tot_dist += dist
    answer = min(answer, tot_dist)
print(answer)

---