[백준] 14502번 연구소(파이썬)

난이도 : GOLD IV

문제링크 : https://www.acmicpc.net/problem/14502

문제해결 아이디어

• 먼저 벽을 꼭 3개를 세워야하므로 벽을 3개 세웠을 때 바이러스를 퍼트려야한다.
• 바이러스는 상하좌우의 인접한 빈칸으로 이동하므로 bfs를 여기서 사용한다.
• 바이러스의 위치를 큐에 전부 넣고 while q를 돌린다.
• 바이러스를 퍼트린 후에 0(빈칸) 이 몇개있는지 체크하고, 최대값을 찾는다.

소스코드

import sys
from collections import deque
import copy

input = sys.stdin.readline

def virus():
  global ans
  g = copy.deepcopy(graph)
  # g = graph[:]
  q = deque()
  for i in range(n):
    for j in range(m):
      if g[i][j] == 2:
        q.append((i,j))

  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 g[nx][ny] == 0:
        g[nx][ny] = 2
        q.append((nx,ny))


  cnt = 0
  for i in range(n):
    for j in range(m):
      if g[i][j] == 0:
        cnt += 1

  ans = max(ans, cnt)

def wall(cnt):
  if cnt == 3:
    virus()
    return

  for i in range(n):
    for j in range(m):
      if graph[i][j] == 0:
        graph[i][j] = 1
        wall(cnt+1)
        graph[i][j] = 0
n,m = map(int, input().split())
graph = []
dx = [1,-1,0,0]
dy = [0,0,-1,1]
ans = 0

for _ in range(n):
    graph.append(list(map(int,input().split())))

wall(0)
print(ans)