[백준 12851번] 연구소 (Python3)

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

N,M = map(int,input().split())

roomorg = []
for i in range(N):
  roomorg.append(list(map(int,input().split())))

dy = [1,-1,0,0]
dx = [0,0,1,-1]

dq = deque()

def virus():
  dq = deque()
  for i in range(N):
    for j in range(M):
      if room[i][j] == 2:
        dq.append((i,j))
        room[i][j] = 0

  while dq:
    y,x = dq.popleft()
    if room[y][x] == 2:
      continue
    room[y][x] = 2
    for i in range(4):
      y1 = y+dy[i]
      x1 = x+dx[i]
      if y1>=0 and y1<N and x1>=0 and x1<M:
        if room[y1][x1] == 0:
          dq.append((y1,x1))

def check():
  count = 0
  for i in range(N):
    for j in range(M):
      if room[i][j] == 0:
        count+=1
  return count

zero = deque()
for i in range(N):
  for j in range(M):
    if roomorg[i][j] == 0:
      zero.append((i,j))

result = 0
for i in list(combinations(zero,3)):
  room = copy.deepcopy(roomorg)
  for j in i:
    y,x = j
    room[y][x] = 1
  virus()
  result = max(result,check())

print(result)

전형적인 BFS 문제이다.

맵을 돌면서 바이러스 위치를 찾고, 벽 3개를 세우는 모든 경우의 수에 대해서 virus 함수를 실행한 뒤 남는 영역의 값을 구하면 된다.

 

알고리즘 자체는 생각하기 쉬운데, 이게 너무 비효율적인 알고리즘이다 보니까 (매번 전체 그래프에 대한 deepcopy를 해주고, 모든 그래프를 다 돌아다니면서 지점을 찾고 등등) 이게 맞나 싶었는데, 맞더라... 괜히 그래프 크기를 15로 제한한게 아니었다.

 

굳이 다른 사람들과의 차이점이라고 한다면 나는 벽을 세우는걸 이전 문제에서 배웠던 itertools의 combinations를 활용했고, 다른 사람들은 백트래킹을 사용했다는거 정도?

 

 

오늘의 교훈) 때로는 가장 비효율적으로 보이는 알고리즘이 정답이다.