[백준] 15686 - 치킨 배달 [Python(파이썬)]

문제

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

15686번: 치킨 배달

 

풀이

처음엔 그래프만 보고 바로 너비 우선 탐색으로 풀었는데, 시간초과가 떴다. 다시 보니 치킨 거리를 구하는 데엔 O(1)로 충분하기 때문에 그래프 탐색이 필요없는 문제였다.

 

입력을 받을 때 집(1)과 치킨집(2)의 좌표를 저장한다. 조합을 이용해 m개의 치킨집(2)을 선택한 후, 각 집마다의 치킨 거리를 구한다(여기선 m이 작기 때문에 min함수를 이용했다). 그 다음 도시의 치킨 거리(치킨거리의 합)를 구하고, 여기서 최솟값을 도출하면 된다.

 

코드

import sys
from itertools import combinations

n, m = map(int, sys.stdin.readline().split())
g = []
houses = []
shops = []
for i in range(n): # 입력을 받을 때 집(1)과 치킨집(2)의 좌표를 저장한다
    row = []
    for j, x in enumerate(sys.stdin.readline().split()):
        if int(x) == 1:
            houses.append((i, j))
        elif int(x) == 2:
            shops.append((i, j))
        raw.append(int(x))
    g.append(raw)

result = []
for picked_shops in list(combinations(shops, m)):
    city_chicken_dist = 0
    for hy, hx in houses:
        dists = []
        for sy, sx in picked_shops:
            dist = abs(hy-sy) + abs(hx-sx)
            dists.append(dist)
        city_chicken_dist += min(dists) # 각 집의 치킨거리를 더해준다
    result.append(city_chicken_dist)

print(min(result))