[알고리즘] 백준 - 17142 (연구소 3) / 파이썬

import sys
from collections import deque
from itertools import combinations
from copy import deepcopy
N , M = map(int , sys.stdin.readline().split())


array = [[0] * N for _ in range(N)]
queue = deque([])
vinum = 0
for i in range(N):
    temp = list(map(int,sys.stdin.readline().split()))
    for j in range(N):
        if(temp[j] ==1):
            array[i][j] = '-'
        elif (temp[j] == 2):
            queue.append([j, i,1])
            array[i][j] = '*'
        else:
            array[i][j] = temp[j]
            vinum +=1

if(vinum==0):
    print(0)
    exit(0)
dx = [1,-1,0,0]
dy = [0,0,1,-1]

def BFS(candqueue , array ,vinum , maxDays):
    while candqueue:
        pop = candqueue.popleft()
        x = pop[0]
        y = pop[1]
        day = pop[2]
        if(day >= maxDays):
            return 2500
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if(0<= nx < N and 0<= ny < N and (array[ny][nx] == 0 or array[ny][nx] == '*')):
                if(array[ny][nx] == 0):
                    vinum -= 1
                    if(vinum== 0):
                        return day
                array[ny][nx] = day +1
                candqueue.append([nx,ny,day+1])


    return 2500

virus = deque(queue)
cand = combinations(virus , M)
maxDays = N**2
for c in cand:
    candQueue = deque([])
    mapArray = deepcopy(array)
    for item in c:
        x = item[0]
        y = item[1]
        candQueue.append(item)
        mapArray[y][x] = 1
    day =  BFS(candQueue, mapArray, vinum , maxDays )
    maxDays = min( day , maxDays)

if(maxDays >= N**2):
    print(-1)
else:
    print(maxDays)

바이러스 후보들을 combinations 를 활용해서 구한 뒤 deepcopy한 map을 가지고 BFS를 사용하며 최솟값을 찾는 문제 한번에 맞긴 했는데 계속 고쳐가면서 하다보니 스파게티 코드 완성