https://www.acmicpc.net/problem/14502
https://github.com/stellaluminary/Baekjoon
해당 문제는 3개의 벽을 세워 바이러스를 막는 것이 목적입니다.
그리고 벽을 잘 세워야 최대한의 빈 칸 0을 많이 만드는 것이 추가적으로 고려해야 하는 부분입니다.
어떻게 고민하다가 그냥 모든 것을 다 계산해버리자는 생각(brute force)을 해버리게 됩니다.
zero 위치를 모두 계산하여 list에 저장해놓고 3개씩 뽑는 조합을 만들었습니다.
그리고 해당 조합 list를 기반으로 벽을 세우고 바이러스를 만났을 때 전파된 이후의 0의 개수를 세도록 하였습니다.
저장해놓은 살아남은 빈 공간의 최대값을 출력하는 것으로 본 문제를 해결하였습니다.
시간이 오래걸려 안 될줄 알았는데 되네요.
from collections import deque
from itertools import combinations
import copy
import sys
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(i, j):
q = deque()
q.append((i, j))
while q:
x, y = q.popleft()
table[x][y] = 2
for k in range(4):
nx, ny = x + dx[k], y + dy[k]
if 0<=nx<n and 0<=ny<m:
if table[nx][ny] == 0:
table[nx][ny] = 2
q.append((nx,ny))
n, m = map(int, input().split())
l = []
for i in range(n):
l.append(list(map(int, input().split())))
zero_loc = []
for i in range(n):
for j in range(m):
if l[i][j] == 0:
zero_loc.append((i,j))
three_loc = list(combinations(zero_loc, 3))
res = []
for tl in three_loc:
table = copy.deepcopy(l)
for idx in tl:
table[idx[0]][idx[1]] = 1
for i in range(n):
for j in range(m):
if table[i][j] == 2:
bfs(i, j)
cnt = 0
for i in range(n):
for j in range(m):
if table[i][j] == 0:
cnt += 1
res.append(cnt)
print(max(res))
from collections import deque
import copy
import sys
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
q = deque()
table = copy.deepcopy(l)
for i in range(n):
for j in range(m):
if table[i][j] == 2:
q.append((i,j))
while q:
x, y = q.popleft()
for k in range(4):
nx, ny = x + dx[k], y + dy[k]
if 0<=nx<n and 0<=ny<m and table[nx][ny] == 0:
table[nx][ny] = 2
q.append((nx,ny))
global ans
cnt = 0
for i in range(n):
cnt += table[i].count(0)
ans = max(ans, cnt)
def rec_wall(num):
if num == 3:
bfs()
return
for i in range(n):
for j in range(m):
if l[i][j] == 0:
l[i][j] = 1
rec_wall(num + 1)
l[i][j] = 0
n, m = map(int, input().split())
l = []
for i in range(n):
l.append(list(map(int, input().split())))
ans = 0
rec_wall(0)
print(ans)