[백준]14502번: 연구소

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

14502번: 연구소

---

일단 보자마자 bfs라는 생각이 들었다

 

벽을 어떻게 세울지가 고민이 많이 됐었다.

시간제한도 2초로 널널하고, n과 m도 8이하로 매우 작긴 하지만

그래도 다 해보는 건 좀 오바라는 생각이 들었기 때문임.

 

그런데 다 해보는 거 말고는 다른 아이디어가 도저히 떠오르지 않아서 다 해봤다.

코드는 좀 더럽지만, 다행히 정답 판정 받긴 했음.

from itertools import combinations
from collections import deque
import sys 
input = sys.stdin.readline

n,m = map(int,input().split())
arr=[]
for i in range(n):
  arr.append(list(map(int,input().split())))

벽을 세울 좌표들 조합 리스트 만들기
zero=[]
for i in range(n):
  for j in range(m):
    if arr[i][j]==0:
      zero.append((i,j))
combi = list(combinations(zero,3))

answer=0
q=deque()
dx,dy = [-1,1,0,0],[0,0,1,-1]
arr2=[[0]*m for _ in range(n)]
for c in range(len(combi)):
  #배열 값 복사해주기
  for i in range(n):
    for j in range(m):
      arr2[i][j]=arr[i][j]
      if arr[i][j]==2:
        q.append((i,j))
  p1,p2,p3=combi[c]
  #벽세우기
  arr2[p1[0]][p1[1]]=1
  arr2[p2[0]][p2[1]]=1
  arr2[p3[0]][p3[1]]=1

  #bfs-->바이러스 감염시키기
  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 arr2[nx][ny]==0:
        arr2[nx][ny]=2
        q.append((nx,ny))

  #안전영역 세기
  cnt=0
  for i in range(n):
    for j in range(m):
      if arr2[i][j]==0:
        cnt+=1
  answer = max(answer,cnt)

print(answer)