[골드5] 14502번 : 연구소

🛠 문제

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

👩🏻‍💻 해결 방법

울타리를 3개 설치하는 것은 dfs에 count 인자를 주고 dfs를 재귀호출하여 모든 경우의 수를 확인해주었다
울타리가 3개 설치됐을 경우, virus를 퍼트리는 함수를 실행하고 이후에 get_score 함수를 통해 안전영역을 구해주면서 최댓값을 갱신해나갔다

소스 코드

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]
temp = [[0] * m for _ in range(n)]

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

result = 0

def virus(x, y):
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    if 0 <= nx < n and 0 <= ny < m:
      if temp[nx][ny] == 0:
        temp[nx][ny] = 2
        virus(nx, ny)

def get_score():
  score = 0
  for i in range(n):
    for j in range(m):
      if temp[i][j] == 0:
        score += 1
  return score

# 울타리를 설치, 울타리가 3개면 안전 영역 계산
def dfs(count):
  global result
  if count == 3:
    for i in range(n):
      for j in range(m):
        temp[i][j] = data[i][j]
    
    for i in range(n):
      for j in range(m):
        if temp[i][j] == 2:
          virus(i, j)
    
    result = max(result, get_score())
    return result

  for i in range(n):
    for j in range(m):
      if data[i][j] == 0:
        data[i][j] = 1
        count += 1
        dfs(count)
        data[i][j] = 0
        count -= 1

dfs(0)
print(result)