[백준] 15686 - 치킨 배달 (구현, 브루트포스)

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

15686번: 치킨 배달

from itertools import combinations
 
n, m = map(int, input().split())
graph = [[0] for _ in range(n + 1)]
homes = list()
stores = list()
 
for i in range(1, n + 1):
    graph[i] += list(map(int, input().split()))
    for j in range(1, n + 1):
        if graph[i][j] == 1:
            homes.append((i, j))
        elif graph[i][j] == 2:
            stores.append((i, j))
 
answer = int(1e9)
combs = combinations(stores, m)
 
for comb in combs:
    town_chicken = 0
    for home in homes:
        chicken = int(1e9)
        for store in comb:
            dist = abs(home[0] - store[0]) + abs(home[1] - store[1])
            if chicken > dist:
                chicken = dist
        town_chicken += chicken
    if answer > town_chicken:
        answer = town_chicken
print(answer)

구현문제이다.

뭔가 효율적인 방법이 없을까 고민했지만, N과 M의 입력 크기 제한을 보니 그냥 브루트포스가 답인 것 같다.

파이썬의 경우에는 combinations를 사용해서 쉽게 풀 수 있다. 다른 언어로는 재귀로 풀어야 할 것 같다.