문제

입력

출력

문제풀이 - DFS : Pypy3로 성공

• 백트래킹으로 하나하나 벽을 세운 후, 그 때의 안전영역 크기를 구해 최댓값을 저장하는 방식으로 접근해야 된다는 생각을 했다.
• 처음에는 값이 '0'인 방들의 index를 조합(collections)을 이용해 벽을 세우는 방식을 떠올렸으나, 이후 풀이가 안 떠올라 포기했다.
• DFS 알고리즘으로 접근하기로 했다.

바이러스를 퍼트리는 함수

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

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

안전영역 크기 구하는 함수

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

전체 코드

# 연구소
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(n)]
tmp = [[0]*m for _ in range(n)]
answer = 0

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

def infect(x,y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
       
        if 0 <= nx < n and 0 <= ny < m and tmp[nx][ny] == 0:
            tmp[nx][ny] = 2
            infect(nx, ny)

def count():
    temp = 0
    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 0:
                temp += 1
    return temp
               
def dfs(w):
    global answer 
   
    if w == 3: # 벽을 다 세우면
        for i in range(n):
            for j in range(m):
                tmp[i][j] = array[i][j] # copy
               
        for i in range(n):
            for j in range(m):
                if array[i][j] == 2:
                    infect(i,j)
        answer = max(answer, count())
        return
    for i in range(n):
        for j in range(m):
            if array[i][j] == 0:
                array[i][j] = 1 # 벽 세우기
                w += 1
                dfs(w)
                array[i][j] = 0 # 세운 벽 거두기
                w -= 1

dfs(0)
print(answer)

다른 풀이 - BFS : Python3로 성공

• 처음 생각했던 방법으로, 조합으로 벽을 세울 수 있는 3군데 리스트로 뽑아내기
• 조합 순회하면서 벽을 세우고, 바이러스 퍼트린 뒤, 안전영역 크기 구하기

import sys
from itertools import combinations
from collections import deque
import copy

input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
points = []
virus = []
answer = 0

def three_point(points): # 벽 세울 곳 
    new_wall = list(combinations(points, 3))
    return new_wall

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

def bfs(graph, points):
    for i, j in points: # 벽 세우기
        graph[i][j] = 1

    queue = deque()
    for v in virus:
        queue.append(v)

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

    count = 0
    for k in range(n): # 안전영역 크기 구하기
        count += graph[k].count(0)

    return count

for i in range(n):
    for j in range(m): # 리스트 순회하면서 
        if graph[i][j] == 0:
            points.append((i, j)) # 벽 세울 수 있는 곳 
        elif graph[i][j] == 2:
            virus.append((i, j)) # 바이러스 있는 곳

new_wall = three_point(points) # 벽 세울 수 있는 곳 조사하기

for p in new_wall:
    new_graph = copy.deepcopy(graph)
    answer = max(answer, bfs(new_graph, p))

print(answer)