[백준] 15686 치킨 배달, python

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

15686번: 치킨 배달

import sys; sys.stdin.readline
from itertools import combinations

N, M = map(int, input().split())
_map = []
house = []
restaurant = []
for i in range(N):
    tmp = list(map(int, input().split()))
    _map.append(tmp)
    for j in range(N):
        if tmp[j] == 1:
            house.append((i, j))
        elif tmp[j] == 2:
            restaurant.append((i, j))
distances = [[0 for _ in range(len(restaurant))] for _ in range(len(house))]

for i in range(len(house)):
    for j in range(len(restaurant)):
        distances[i][j] = abs(house[i][0]-restaurant[j][0]) + abs(house[i][1]-restaurant[j][1])

answer = 100000000
for range_list in combinations(range(len(restaurant)),M):
    tmp = 0
    for i in range(len(house)):
        min_val = 100000000
        for j in range_list:
            if min_val > distances[i][j]:
                min_val = distances[i][j]
        tmp += min_val
    if answer > tmp:
        answer = tmp
print(answer)

주어진 치킨집중에 M개를 골라서 모든 집과 치킨집의 거리의 합 중 최소값을 찾는 문제이다.

이 문제를 풀 때 총 세단계로 나누었다.

1) 집(1)과 치킨집(2)의 위치를 각각 house와 restaurant에 저장한다.

2) 집 기준으로 치킨집까지의 거리를 계산한다.

이때 거리는 문제에 나와있듯 좌표간의 차이(절댓값)를 더해서 구한다.

3) M개의 치킨집을 고를때 최소 거리를 구해서 출력한다.

이 부분에서 시간이 많이 걸렸는데 M개를 고르는 문제이므로 backtracking을 사용할까하다가 구현을 못해서 itertools.combinations를 사용해서 구현하였다. M개의 치킨집 중에서 각 집에서 가장 가까운 치킨집까지 거리를 더하고 그 값이 answer보다 작은 경우에만 갱신을 시켜주었다.

Brute-force 방식으로 구현했는데 경우의 수가 생각보다 적게 나와서 (13*12*11 정도?) 통과할수 있었다.