[BOJ] 백준 14502 연구소 Python

from collections import deque
from itertools import combinations
import copy

N,M = map(int,input().split())
block = []
empty = []
virus = []
for i in range (0,N):
    A = list(map(int,input().split()))
    for j in range (0,M):
        if A[j] == 0:
            empty.append([i,j])
        if A[j] == 2:
            virus.append([i,j])
    block.append(A)
ans = 0
for x in combinations(empty,3):
    cnt = 0
    x = list(x)
    B = copy.deepcopy(block)
    B[x[0][0]][x[0][1]],B[x[1][0]][x[1][1]], B[x[2][0]][x[2][1]]  = 1,1,1
    dx,dy = [0,0,-1,1],[1,-1,0,0]
    deq = deque()
    for i in range (0,len(virus)):
        deq.appendleft(virus[i])
    while deq:
        y = deq.popleft()
        for i in range (0,4):
            z = y[0] + dx[i]
            w = y[1] + dy[i]
            if 0 <= z < N and 0 <= w < M and B[z][w] == 0:
                B[z][w] = 2
                deq.append([z,w])
    for i in range (0,N):
        for j in range (0,M):
            if B[i][j] == 0:
                cnt += 1
    ans = max(ans,cnt)
print(ans)

 

생각보다 클린코드가 나와서 좋았던 것 같습니다. 

 

바이러스가 옮겨질 조건은, 아무것도 없는 0인 공간에 한하므로, B[z][w]에서 적절하게 이용하면 좋을 것 같습니다.

결국 벽 3개라는 조건이 주어졌으므로, 브루트포스를 통해서 문제를 해결할 수 있었습니다.

 

문제를 살짝 응용한다면, 벽 하나를 세우는데 cost가 들 때, 최적의 cost - safety area를 컨트롤 하는 방법도 있겠습니다.

오히려 이쪽이 더 재밌을 것 같은 느낌이네요. 대신 이렇게 된다면 난이도는 조금 더 올라갈지도 ... ? 

 

(벽 갯수를 다시 제한하는 방식 등등으로...)