백준 17141: 연구소 2 [Python]

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

17141번: 연구소 2

코드

import itertools
import sys
import queue
 
n, m = map(int, sys.stdin.readline().split())
lis = []
two_cnt = 0
two_point = []
for i in range(n): lis.append(list(map(int, sys.stdin.readline().split())))
for i in range(n):
    for j in range(n):
        if lis[i][j] == 2: 
            two_cnt += 1
            two_point.append([i, j])
            
tmp = [i for i in range(two_cnt)]
d = [[1, 0], [0, 1], [-1, 0], [0, -1]]
q = queue.Queue()
 
ans = sys.maxsize
for combination in itertools.combinations(tmp, m):
    check = True
    value = [[0 for i in range(n)] for j in range(n)]
    for combi in combination: 
        value[two_point[combi][0]][two_point[combi][1]] = 1
        q.put(two_point[combi] + [1])
    
    while q.empty() == False:
        v = q.get()
        for i in d:
            if v[0] + i[0] < n and v[0] + i[0] >= 0 and v[1] + i[1] < n and v[1] + i[1] >= 0:
                if lis[v[0] + i[0]][v[1] + i[1]] != 1 and value[v[0] + i[0]][v[1] + i[1]] == 0:
                    value[v[0] + i[0]][v[1] + i[1]] = v[2] + 1
                    q.put([v[0] + i[0], v[1] + i[1], v[2] + 1])
    
    t = 0
    for i in range(n):
        for j in range(n):
            if lis[i][j] == 1: value[i][j] = -1
            if value[i][j] == 0: check = False
    
    if check: ans = min(ans, max(map(max, value)))
print(ans - 1 if ans != sys.maxsize else -1)

풀이

1. 일반적인 2차원 평면 위의 BFS를 구현합니다

2. 바이러스 위치를 저장 후 itertools.combinations로 가능 한 모든 바이러스의 위치를 표시 합니다.