백준
백준 14502 연구소 (파이썬)
chldkato
2020. 2. 16. 20:57
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
www.acmicpc.net
벽을 세울 수 있는 공간에 벽 3개를 세우는 모든 경우에 대해서
각 경우마다 BFS로 바이러스를 퍼뜨린 후 안전영역을 구하면 되는 문제
import sys
import copy
from collections import deque
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
ans = 0
def bfs():
global ans
w = copy.deepcopy(a)
for i in range(n):
for j in range(m):
if w[i][j] == 2:
q.append([i, j])
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if w[nx][ny] == 0:
w[nx][ny] = 2
q.append([nx, ny])
cnt = 0
for i in w:
cnt += i.count(0)
ans = max(ans, cnt)
def wall(x):
if x == 3:
bfs()
return
for i in range(n):
for j in range(m):
if a[i][j] == 0:
a[i][j] = 1
wall(x+1)
a[i][j] = 0
n, m = map(int, sys.stdin.readline().split())
a = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
q = deque()
wall(0)
print(ans)