[백준 15686] 치킨배달

접근

문제의 입력조건이 작아 모든걸 탐색하는 brute force 알고리즘을 사용할수있음을 추측할수있다.

일단 M개의 치킨집에 대한 모든 조합을 구해 list에 담은뒤에

해당리스트를 순회하며 해당 치킨집들이 선택되었을때 도시의 치킨거리를 구하여 answer배열에 담아준다

이후 answer배열중 min값을 택하여 출력해준다.

• from itertools import combinations
• for i, value in enumerate()

위두가지를 잘 사용

코드

from itertools import combinations
N,M = map(int,input().split())
m = [list(map(int,input().split())) for _ in range(N)]
answer = []
cnt = 0
chicken = []
for i in range(N):
    if 2 in m[i]:
        cnt += m[i].count(2)
        l = [i for i, value in enumerate(m[i]) if value == 2]
        for o in l:
            chicken.append([i,o])

chicken = list(combinations(chicken,M))
for x in chicken:
    d = []
    for i in range(N):
        for j in range(N):
            if m[i][j] == 1:
                dist = []
                for y in x:
                    a, b = y
                    dist.append(abs(i - a) + abs(j - b))
                d.append(min(dist))
    answer.append(sum(d))
print(min(answer))