백준 치킨 배달 코드 및 해설 (파이썬)

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

15686번: 치킨 배달

 

국어 능력이 중요한 거 같은 복잡한 문제!!!! 

우선 입력으로 들어온 걸 잘 정리해서 저장해둔다

N은 도시 크기, M은 최종 선택할 치킨 가게 개수, houses엔 집이 있는 좌표를 튜플로, stores엔 치킨 가게가 있는 좌표를 튜플로 저장한다. 이때 좌표는 0이 아니라 1부터 시작한다고 했으므로 그냥 +1씩 해줬다.

이후 각 집마다 각 치킨 가게까지의 거리를 구했다. 이를 딕셔너리로 저장했다. key가 집의 좌표, value는 각 치킨가게로부터의 거리의 리스트

이후 M의 값에 따라 다르게 계산한다. 현재 치킨 가게 개수랑 M이랑 같은 경우 아무것도 제외할 필요없이 그냥 지금까지 구한 치킨 거리들 중 각 집에서의 최솟값을 모두 더해 답으로 반환하면 된다. 

M이 현재 치킨 가게 개수보다 작으면 약간 귀찮다. combinations로 M개를 선택하는 모든 경우의 수를 구한 후, 각 경우의 수마다의 치킨 거리를 구한다. 예를 들어 현재 치킨 가게는 5개고 M은 2라면 0,1,2,3,4의 치킨 가게 중 2개를 고르는 경우의 수는 (0,1), (0,2), ... (3,4) 등이 있다. 이때 (0,1) 경우의 수가 걸리면 각 집에서 치킨 가게까지의 거리 중 0번째, 1번째의 거리만 비교해서 이 중 최솟값을 치킨 거리로 선택해야 한다. 이런 식으로 각 경우의 수마다 치킨 거리를 구하고 이중 최솟값을 최종 답으로 반환한다.

 

import sys
from itertools import combinations

# N: 도시 크기
# M: 최종 선택할 치킨가게 개수 
N, M = map(int, sys.stdin.readline().split())
city = []
houses = []  # 집 좌표
stores = []  # 치킨가게 좌표
for i in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    for j in range(len(row)):
        if row[j] == 1:
            houses.append((i + 1, j + 1))
        if row[j] == 2:
            stores.append((i + 1, j + 1))
    city.append(row)

# 각 집마다 각 치킨가게까지의 거리를 저장한 딕셔너리 
dist = {}
for house in houses:
    x, y = house
    dist[house] = []
    for store in stores:
        a, b = store
        dist[house].append(abs(x - a) + abs(y - b))

# 존재하는 모든 치킨가게를 선택할 경우 
if len(stores) == M:
    answer = 0
    for h in dist:
        # 각 집마다의 거리 중 최소 거리를 더해 답으로 반환
        answer += min(dist[h])
    print(answer)
# 일부 치킨가게만 선택할 경우 
else:
    # M개를 선택하는 모든 경우의 수에 따른 치킨 거리
    combs = list(combinations(list(range(len(stores))), M))
    candidates = []
    for comb in combs:
        ans = 0
        for h in dist:
            ans += min([dist[h][idx] for idx in comb])
        candidates.append(ans)
    # 모든 치킨 거리 중 최솟값을 답으로 반환
    print(min(candidates))