📌 [BOJ] 백준 14502 연구소

📖 문제

📖 예제

📖 풀이

from collections import deque
import sys
import copy

N, M = map(int, input().split())
graph = []
ans = 0
for _ in range(N):
  graph.append(list(map(int,sys.stdin.readline().split())))

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

def make_Wall(wall):
  if wall == 3:
    BFS()
    return
  for i in range(N):
    for j in range(M):
      if graph[i][j] == 0:
        graph[i][j] = 1
        make_Wall(wall+1)
        graph[i][j] = 0

def BFS():
  tmp_graph = copy.deepcopy(graph)
  queue = deque()
  for i in range(N):
    for j in range(M):
      if tmp_graph[i][j] == 2:
        queue.append((i,j))

  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x+dx[i]
      ny = y+dy[i]
      if 0<=nx<N and 0<=ny<M and tmp_graph[nx][ny] == 0:
        tmp_graph[nx][ny] = 2
        queue.append((nx,ny))

  cnt = 0
  for i in range(N):
    for j in range(M):
      if tmp_graph[i][j] == 0:
        cnt += 1
  global ans
  ans = max(ans, cnt)

make_Wall(0)
print(ans)

1. make_wall: backtracking 방식으로 값이 0인 위치에 벽을 세워 3개의 벽이 세워졌을 때 마다 BFS 함수를 호출한다.
2. BSF: copy를 통해 기존 그래프를 복사해놓은 데이터를 사용한다.
   큐 자료구조를 활용해 값이 2인 위치로부터 탐색 가능한 0의 값을 갖는 위치 값을 2로 갱신한다. 그런 뒤 마지막에 오염되지 않은 영역의 수를 세어 기존 안전 영역 값과 비교하여 최대값으로 갱신한다.