문제 설명

->링크<-

해결 방법

먼저 N과 M의 크기가 매우 작은 것이 눈에 들어왔고 읽어 봤을 때
벽 3개를 무조건 세워야하며 이부분을 어떻게 해결할까 고민중 처음에 생각 해본 방법은 3중 for문이었지만 그것보다 combination함수를 이용하면 훨씬 간단해 보였다 이때 시간 복잡도는 combination(64,3)보다 작기 때문에 시간제한 2초는 넉넉했다. 또한 이 모든 경우에서 BFS를 돌려야 하는데
이때 각 BFS도 64연산 횟수를 넘기지 않기 때문에 최대 연산횟수는 바로

combination(64,3) X 64가 되고 이는 약 1600만이고
2초내에 충분히 해결 할 수 있었다.

간단히 간추려보면

1. 문제 조건에 따라 연구소 정보를 입력받는다.
2. combination함수로 벽을 3개 세울 수 있는 모든 경우의수 내에서
3. BFS함수를 통해 안전영역을 도출해낸다

해답 코드

from collections import deque
from itertools import combinations
import sys
import copy
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
def BFS(new_matrix):
  #바이러스 찾기
  for i in range(N):
    for j in range(M):
      if new_matrix[i][j] == 2:
        Q = deque()
        Q.append((i,j))
        while Q:
          Y, X = Q.popleft()
          for d in range(4):
            curY = Y + dy[d]
            curX = X + dx[d]
            #새로운 방향이 matrix를 벗어나지 않을 경우 
            if curY >= 0 and curY < N and curX >= 0 and curX < M:
              if new_matrix[curY][curX] == 0:
                Q.append((curY, curX))
                new_matrix[curY][curX] = 3
  res = 0
  for i in range(N):
    for j in range(M):
      if new_matrix[i][j] == 0:
        res+=1
  return res
              
input = sys.stdin.readline
N, M = map(int, input().split())
matrix = []
for i in range(N):
  matrix.append(list(map(int, input().split())))
#빈공간의 정보를 입력받는 리스트
empty_list = list()
for i in range(N):
  for j in range(M):
    if matrix[i][j] == 0:
      empty_list.append((i,j))
result = -1
for combi in combinations(empty_list, 3):
  first, second, third = combi
  #matrix를 new_matrix로 복사
  new_matrix = copy.deepcopy(matrix) 
  #새로운 벽 생성
  new_matrix[first[0]][first[1]] = 1
  new_matrix[second[0]][second[1]] = 1
  new_matrix[third[0]][third[1]] = 1

  tmp = BFS(new_matrix)
  result = max(result, tmp)

print(result)

걸린시간

다른 사람의 코드를 보고난 후

벽을 재귀함수를 통해 구현하는 방법도 있었다.
생각보다 걔념2가지 (조합과 BFS)만 확실히 잡혀있다면 충분히 어렵지 않은 문제였다. 다른사람의 코드는 조합함수를 사용했는가 재귀함수를 사용했는가의 차이말고는 없었다.