NM 크기의 연구소에 11인 각 칸은 빈칸 또는 벽으로 이루어져있음. 일부 칸은 바이러스가 존재하고, 바이러스는 상하좌우 인접한 빈칸으로 퍼져나감. 벽을 딱 3개만 세워서 얻을 수 있는 바이러스가 퍼질 수 없는 안전 영역 크기의 최대값은?
IN
N M
지도의 모양 (0:빈칸, 1:벽, 2:바이러스)
OUT
안전 영역의 최대 크기
빈칸중 3개 고르기 → combination
바이러스 퍼뜨리기 → BFS 이용
import sys
import copy
from collections import deque
input = sys.stdin.readline
answer = 0
n, m = map(int, input().split())
lab = []
for i in range(n):
l = list(map(int, input().split()))
lab.append(l)
def check(lab):
queue = deque()
for i in range(n):
for j in range(m):
if lab[i][j] == 2:
queue.append([i,j])
print(queue)
while queue:
i,j = queue.popleft()
if i-1>=0 and lab[i-1][j] == 0:
lab[i-1][j] = 2
queue.append([i-1, j])
if i+1<n and lab[i+1][j] == 0:
lab[i+1][j] = 2
queue.append([i+1, j])
if j-1>=0 and lab[i][j-1] == 0:
lab[i][j-1] = 2
queue.append([i, j-1])
if j+1<m and lab[i][j+1] == 0:
lab[i][j+1] = 2
queue.append([i, j+1])
print(lab)
def dfs(lab, count):
if count == 3:
global answer
ans = 0
viruslab = copy.deepcopy(lab)
check(viruslab)
for i in range(n):
for j in range(m):
if viruslab[i][j] == 0:
ans += 1
answer = max(answer, ans)
count = 0
else:
for i in range(n):
for j in range(m):
if lab[i][j] == 0:
lab[i][j] = 1
dfs(lab, count+1)
lab[i][j] = 0
dfs(lab, 0)
print(answer)
dfs를 이용하려고 했다. 근데 시간이 엄청 오래걸려서 시초 날거같음
import sys
import copy
from collections import deque
import itertools
input = sys.stdin.readline
answer = 0
n, m = map(int, input().split())
lab = []
empty = []
for i in range(n):
l = list(map(int, input().split()))
for j in range(len(l)):
if l[j] == 0:
empty.append([i,j])
lab.append(l)
def check(lab):
queue = deque()
for i in range(n):
for j in range(m):
if lab[i][j] == 2:
queue.append([i,j])
#print(queue)
while queue:
i,j = queue.popleft()
if i-1>=0 and lab[i-1][j] == 0:
lab[i-1][j] = 2
queue.append([i-1, j])
if i+1<n and lab[i+1][j] == 0:
lab[i+1][j] = 2
queue.append([i+1, j])
if j-1>=0 and lab[i][j-1] == 0:
lab[i][j-1] = 2
queue.append([i, j-1])
if j+1<m and lab[i][j+1] == 0:
lab[i][j+1] = 2
queue.append([i, j+1])
#print(lab)
def solution():
wall = list(itertools.combinations(empty, 3))
global answer
for w in wall:
viruslab = copy.deepcopy(lab)
count = 0
for i in range(3):
viruslab[w[i][0]][w[i][1]] = 1
#print(lab)
check(viruslab)
for i in range(len(viruslab)):
count += viruslab[i].count(0)
answer = max(answer, count)
for i in range(3):
viruslab[w[i][0]][w[i][1]] = 0
solution()
print(answer)
한달이 넘게 지난 오늘 스터디하면서 다시 풀어보았다!
import sys
from collections import deque
from itertools import combinations
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N, M = map(int, input().split())
lab = []
virus_pos = []
empty_pos = []
answer = 0
for i in range(N):
tmp = list(map(int, input().split()))
for j in range(M):
if tmp[j] == 0:
empty_pos.append((i,j))
elif tmp[j] == 2:
virus_pos.append((i,j))
lab.append(tmp)
def in_boundary(x,y):
if x in range(0, N) and y in range(0,M):
return True
else:
return False
def bfs(lab, virus_pos):
#모든 바이러스의 위치를 queue에
queue = deque(virus_pos)
while queue:
#각 바이러스에서
x, y = queue.popleft()
#상하좌우 검사
for i in range(4):
#범위 내에 있고 빈칸이면
if in_boundary(x+dx[i], y+dy[i]):
if lab[x+dx[i]][y+dy[i]] == 0:
#바이러스 퍼뜨리기
lab[x+dx[i]][y+dy[i]] = 2
queue.append((x+dx[i], y+dy[i]))
count = 0
for i in range(N):
count += lab[i].count(0)
for x,y in empty_pos:
lab[x][y] = 0
return count
walls = list(combinations(empty_pos, 3))
for wall in walls:
for x, y in wall:
lab[x][y] = 1
#print(lab)
#바이러스 퍼뜨리기
answer = max(answer, bfs(lab, virus_pos))
for x, y in wall:
lab[x][y] = 0
print(answer)