알고리즘: 백준 15686번 치킨 배달 (feat. python)

 

15686번: 치킨 배달

 

 

import sys
from collections import deque
from itertools import combinations
import copy
read = sys.stdin.readline


N, M = map(int, read().split())
country = []
chick = []


for i in range(N):
    country.append(list(map(int, read().split())))
    for j in range(N):
        if country[i][j] == 2:
            chick.append([0, i, j])


def bfs():
    distance = 0
    d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    visit = copy.deepcopy(country)
    while queue:
        cdist, crow, ccol = queue.popleft()

        if visit[crow][ccol] != -1:
            visit[crow][ccol] = -1
            if country[crow][ccol] == 1:
                distance += cdist
            for i in range(4):
                nrow = crow + d[i][0]
                ncol = ccol + d[i][1]
                if 0 <= nrow < N and 0 <= ncol < N and visit[nrow][ncol] != -1:
                    queue.append([cdist+1, nrow, ncol])

    return distance


min_distance = sys.maxsize

for i in range(1, M+1):
    select_chick = list(combinations(chick, i))
    while select_chick:
        queue = deque(select_chick.pop())
        min_distance = min(min_distance, bfs())
        
print(min_distance)