boj.kr/15686 치킨 배달 (gold5) 파이썬 풀이

1. 집의 좌표들과 치킨집 좌표들을 각각 리스트에 저장
2. combinations를 사용해 치킨집 좌표 리스트에서 추출한 M개의 치킨집 좌표들을 순회하면서 아래(3,4,5)를 반복
3. 집의 좌표 목록을 순회

4. 집에서 치킨집까지 거리를 계산하고 최소 치킨거리를 저장
5. 모든 집들의 최소 치킨거리를 더한 값을 최소 치킨거리 리스트에 저장
6. 최소 치킨거리 리스트에서 최소값을 출력

 

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
chickens = []
homes = []
for y  in range(N):
    for x in range(N):
        if board[y][x] == 2:
            chickens.append((y, x))
        if board[y][x] == 1:
            homes.append((y, x))
def get_d(y1, x2, y2, x1):
    return abs(y2-y1) + abs(x2-x1)

from itertools import combinations
chicken_d_sum_list = []
for combi in combinations(chickens, M):
    chicken_d_sum = 0
    for (hy, hx) in homes:
        min_chicken_d = 1e9
        for (cy, cx) in combi:
            min_chicken_d = min(min_chicken_d, get_d(hy, hx, cy, cx))
        chicken_d_sum += min_chicken_d
    chicken_d_sum_list.append(chicken_d_sum)
print(min(chicken_d_sum_list))

 

최단거리를 구하기 위해 bfs보다 좌표연산하는 것이 더 빠를 수 있다.