14502 연구소

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

14502번: 연구소

#1. 안전지대를 찾는 것은 일반적인 bfs로 찾으면됨 문제는 벽 3개를 어떻게 세울꺼야??
#2. 조합을 이용해서 빈칸에 3개를 세우는 모든 경우의수를 구함 => 즉 벽세우고 bfs돌리기
#import sys
from collections import deque
from itertools import combinations

#주어진 조건 받기
n,m = map(int,input().split())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))
    
blank =[]
virus = []    
#방향설정 상하좌우
dx=[-1,1,0,0]
dy=[0,0,-1,1]

#bfs함수 만들기
result = 0
def bfs():
    global result
    #안전지대에서 벽3개 세웠으니 3개 빼줘야함
    cnt = len(blank)-3
    #바이러스인 애들
    q= deque(virus)
    #print(q)
    #for x,y in virus:
    #    q.append((x,y))
    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 and new_graph[nx][ny]==0:
                #바이러스 감염으로 바꿔주고
                new_graph[nx][ny]=2
                #큐에 넣어주고
                q.append((nx,ny))
                #안전지대 빼주고
                cnt-=1
    result = max(result,cnt)
                
    
#벽세울수 있는 곳 받기 

for i in range(n):
    for j in range(m):
        if graph[i][j]==0:
            blank.append((i,j))
        elif graph[i][j]==2:
            virus.append((i,j))
#가능한 조합들
possi = combinations(blank,3)
from copy import deepcopy

for new in possi:
    new_graph = deepcopy(graph)
    #벽세우기
    for x,y in new:
        new_graph[x][y]=1
    bfs()
        
print(result)