[구현 문제] 백준 15686번: 치킨 배달 / 골드 5

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

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

import itertools
import sys
n, m = map(int, input().split())

graph = []
house = []
shop = []
for i in range(n):
    row = list(map(int, input().split()))
    for j in range(n):
        if row[j] == 1:
            house.append([i, j])
        elif row[j] == 2:
            shop.append([i, j])
    graph.append(row)

def dist(p1,p2):
    x1, y1 = p1[0], p1[1]
    x2, y2 = p2[0], p2[1]
    return abs(x1-x2) + abs(y1-y2)

combi = list(itertools.combinations(shop,m))
results = []

for i in range(len(combi)):
    case = combi[i] # one of the combination cases
    distances = []
    for j in range(len(house)):
        min_dist = sys.maxsize
        for k in range(m):
            min_dist = min(min_dist, dist(house[j], case[k]))
        distances.append(min_dist)
    results.append(sum(distances))
print(min(results))

이 문제의 트릭 아닌 트릭이라면 치킨집을 최대 M개 남겨놓을 수 있다고 하는데,

이러면 치킨집이 1개인 경우부터 M개인 경우까지 다 봐야하나? 생각할 수 있지만

사실 M개인 경우만 살펴보면 된다. 치킨집 수가 적어질 수록 치킨 거리는 손해볼 수밖에 없기 때문이다.

치킨집 개수 = a

집 개수 = b

aCm* b * m만큼 for문이 돌아간다.