[골드 5] 백준 15686 - 치킨 배달 (파이썬)

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

풀이

도시에는 집(1)과 치킨집(2)가 있고, 나머지는 (0)으로 빈칸이다.

최대 M개의 치킨집만 선택해서 영업해야하며, 모든 집은 가장 가까운 치킨집까지의 거리로 만족한다.

모든 지들의 치킨 거리의 합이 최소가 되도록 M개의 치킨집을 선택해야한다.

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

N, M, C는 도시의 크기, 영업할 치킨집 수, 도시 지도 정보를 나타낸다.

house = []
chicken = []

for i in range(N):
    for j in range(N):
        if C[i][j] == 1:
            house.append((i, j))
        if C[i][j] == 2:
            chicken.append((i, j))

집과 치킨집의 위치를 각각 리스트에 저장한다.

min_total = 1e9

최소 도시 치킨 거리를 초기화 한다. (엄청 큰수로 선언)

total = 0
for r1, c1 in house:
    min_dist = 1e9
    for r2, c2 in combination:
        min_dist = min(min_dist, abs(r1 - r2) + abs(c1 - c2))
    total += min_dist

현재 선택된 M개의 치킨집 조합에 대해, 각 집이 가장 가까운 치킨집과의 거리(min_dist)를 구하고, 모든 집의 최소 거리의 합을 total로 저장한다.

min_total = min(min_total, total)

지금 조합의 도시 치킨 거리와 이전까지의 최소값을 비교하여 최소값을 갱신합니다.

시간 복잡도 분석

치킨집 수가 최대 13이므로, 가능한 조합 수는 C → 브루트 포스 가능

조합마다 모든 집을 순회하며 거리를 계산한다.

코드

# 백준 15686 - 치킨 배달
# 분류 : 브루트 포스

from itertools import combinations

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

house = []
chicken = []

for i in range(N) :
    for j in range(N) :
        if C[i][j] == 1 :
            house.append((i, j))
        if C[i][j] == 2 :
            chicken.append((i, j))

min_total = 1e9
for combination in combinations(chicken, M) :
    total = 0
    for r1, c1 in house :
        min_dist = 1e9
        for r2, c2 in combination :
            min_dist = min(min_dist, abs(r1 - r2) + abs(c1 - c2))
        total += min_dist
    min_total = min(min_total, total)

print(min_total)