14502 백준 파이썬

요약하면 n*m의 직사각형으로 이뤄진 연구소에 임의의 벽을 세개 세우고, 바이러스를 퍼뜨린다. 그리고 그 때의 안전공간(0)의 수를 출력하면 된다.

 

풀이:

1. dfs를 통해 벽을 세운다.

2. bfs를 통해 바이러스를 퍼뜨린다.

3. 0의 갯수를 센다.

 

치킨거리 문제와 다르게 실제로 벽을 세우고, 시뮬레이션을 돌려야 하기때문에 조금 더 오래 걸린다.

https://0422.tistory.com/62

15686 백준 파이썬

 

코드는 아래와 같다.

import sys
import copy
from collections import deque
input=sys.stdin.readline
n,m=map(int,input().split())
ans=0
space=[]
for _ in range(n):
    a=list(map(int,input().split()))
    space.append(a)
    
def wall(cnt):
    if cnt==3:
        virus()
        return 
    for x in range(n):
        for y in range(m):
            if space[x][y]==0:
                space[x][y]=1
                wall(cnt+1)
                space[x][y]=0
    
def virus():
    global ans
    newspace=copy.deepcopy(space)
    q=deque()
    cnt=0
    for x in range(n):
        for y in range(m):
            if newspace[x][y]==2:
                q.append([x,y])
    while q:
        x,y=q.popleft()
        a=[1,-1,0,0]
        b=[0,0,1,-1]
        for i in range(4):
            X=x+a[i]
            Y=y+b[i]
            if 0<=X<n and 0<=Y<m:
                if newspace[X][Y]==0:
                    newspace[X][Y]=2
                    q.append([X,Y])
    for x in range(n):
        for y in range(m):
            if newspace[X][Y]==0:
                cnt+=1
    cnt=0
    for i in newspace:
        cnt+=i.count(0)
    ans=max(ans,cnt)
    return 


            
wall(0)
print(ans)