162. 연구소

백준

1. Python

DFS

n, m = map(int, input().split())
data = []
temp = [[0] * m for _ in range(n)] #벽 설치 뒤

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

#(북, 동, 남, 서)
dx = [-1, 0 , 1, 0]
dy = [0, 1, 0, -1]

result = 0

#DFS 사방으로 퍼지게
def virus(x, y):
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    #상, 하, 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
    if nx >= 0 and nx < n and ny >= 0 and 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

#DFS로 울타리 설치하면서, 매번 안전 영역 크기 계산
def dfs(count):
  global result
  #울타리가 3개 설치된 경우
  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 
  
  #빈 공간에 울타리 설치
  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)

BFS, combinations

# boj 14502
# blog : jjangsungwon.tistory.com
import sys, copy
import itertools
from collections import deque


def bfs():
    q = deque(virus)
    visited = [[0] * M for _ in range(N)]

    while q:
        row, col = q.popleft()

        # 상
        if row - 1 >= 0 and temp_arr[row - 1][col] == 0 and visited[row - 1][col] == 0:
            visited[row - 1][col] = 1
            temp_arr[row - 1][col] = 2
            q.append([row - 1, col])

        # 하
        if row + 1 < N and temp_arr[row + 1][col] == 0 and visited[row + 1][col] == 0:
            visited[row + 1][col] = 1
            temp_arr[row + 1][col] = 2
            q.append([row + 1, col])

        # 좌
        if col - 1 >= 0 and temp_arr[row][col - 1] == 0 and visited[row][col - 1] == 0:
            visited[row][col - 1] = 1
            temp_arr[row][col - 1] = 2
            q.append([row, col - 1])

        # 우
        if col + 1 < M and temp_arr[row][col + 1] == 0 and visited[row][col + 1] == 0:
            visited[row][col + 1] = 1
            temp_arr[row][col + 1] = 2
            q.append([row, col + 1])


if __name__ == "__main__":

    N, M = map(int, input().split())
    arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

    virus = []
    # 벽을 세울 수 있느 후보
    temp = []
    for i in range(N):
        for j in range(M):
            if arr[i][j] == 0:
                temp.append([i, j])
            elif arr[i][j] == 2:
                virus.append([i, j])  # 바이러스 위치
    result = list(itertools.combinations(temp, 3))

    min_area = -1
    # 후보 개수 만큼 진행
    for k in range(len(result)):
        temp_arr = copy.deepcopy(arr)

        for i in range(3):
            temp_arr[result[k][i][0]][result[k][i][1]] = 1  # 벽 세우기

        # 바이러스 전파 시작
        bfs()

        cnt = 0
        for i in range(N):
            for j in range(M):
                if temp_arr[i][j] == 0:
                    cnt += 1
        min_area = max(min_area, cnt)
    print(min_area)

BFS

import sys
import copy
from collections import deque

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

def bfs():
    global ans
    w = copy.deepcopy(a)
    for i in range(n):
        for j in range(m):
            if w[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:
                if w[nx][ny] == 0:
                    w[nx][ny] = 2
                    q.append([nx, ny])
	#안전영역 세기
    cnt = 0
    for i in w:
        cnt += i.count(0)
    ans = max(ans, cnt)

def wall(x):
    if x == 3:
        bfs()
        return
    for i in range(n):
        for j in range(m):
            if a[i][j] == 0:
                a[i][j] = 1
                wall(x+1)
                a[i][j] = 0

n, m = map(int, sys.stdin.readline().split())
a = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
q = deque()
wall(0)
print(ans)