Baekjoon-14502-연구소
09 Oct 2022그냥 단순히만 봐도 O(2^30)이라는 엄청난 연산량인데, 왜 Brute-force로 동작하는 건지 사실 모르겠다..!!
from collections import deque
import sys
input = sys.stdin.readline
N,M = map(int, input().split())
board = []
viruses = []
empties = []
for n in range(N):
line = list(map(int,input().split()))
board.append(line)
for m in range(M):
if line[m] == 0:
empties.append([n,m])
elif line[m] == 2:
viruses.append([n,m])
def bfs():
visited = [[0] * M for _ in range(N)]
q = deque(viruses)
for x,y in viruses:
visited[x][y] = 1
count = 0
while q:
x,y = q.popleft()
for dx,dy in [[0,1],[1,0],[0,-1],[-1,0]]:
nx,ny = x+dx, y+dy
if 0<=nx<N and 0<=ny<M and visited[nx][ny]==0 and board[nx][ny]==0:
visited[nx][ny] = 1
q.append([nx,ny])
count += 1
if count >= min_polute:
return min_polute+1
return count
# Brute-force -> O(64^5)=O(2^30) -> 너무 크지 않나...?
min_polute = len(empties)
min_walls = []
for i in range(len(empties)-2):
board[empties[i][0]][empties[i][1]] = 1
for j in range(i+1, len(empties)-1):
board[empties[j][0]][empties[j][1]] = 1
for k in range(j+1, len(empties)):
board[empties[k][0]][empties[k][1]] = 1
min_polute = min(bfs(),min_polute)
board[empties[k][0]][empties[k][1]] = 0
board[empties[j][0]][empties[j][1]] = 0
board[empties[i][0]][empties[i][1]] = 0
print(len(empties)-min_polute-3)