연구실에서 바이러스가 유출되었는데 바이러스가 퍼지기 전에 3개의 벽을 세워 바이러스의 침입을 막는다.
바이러스가 가장 적게 퍼지도록 했을 경우의 안전구역 갯수를 반환해보자
- 접근 방법
바이러스가 없는 입력이 0인 구역에서 3개를 뽑아 벽을 세우는 모든 경우의 수를 구한다.
경우의 수마다 3개의 벽을 세웠을 때 안전구역의 개수를 구해 최댓값을 구한다.
- 입출력 예시
- 코드
from itertools import combinations
from collections import deque
from copy import deepcopy
# 바이러스가 있는곳 4방향 탐색
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
# 유효한 범위인지 검사
def is_valid(r, c):
return 0 <= r < n and 0 <= c < m
def BFS():
safe_max = 0 # 안전구역이 가장 많을 때 안전구역의 수
# 바이러스 없는 구역 3곳을 뽑는 경우의 수만큼 반복
for i in safe:
for j in i: # 바이러스 없는 구역 3곳에 벽 설치
v_lab[j[0]][j[1]] = 1
v_q = deepcopy(q) # 반복마다 큐, 실험실 초기상태로 갱신
v_lab = deepcopy(lab)
while v_q: # 큐가 비어있을 때까지 반복
r, c = v_q.popleft() # 바이러스가 있는 구역 pop
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
# 네방향 탐색해서 벽이 아니고 바이러스가 없을경우 바이러스 감염
if is_valid(nr, nc) and v_lab[nr][nc] == 0:
v_lab[nr][nc] = 2
v_q.append((nr, nc)) # 감염시킨 구역을 큐에 추가
# 감염이 끝난 실험실에서 안전구역을 세어 최댓값 갱신
safezone = 0
for i in v_lab:
safezone += i.count(0)
if safe_max < safezone:
safe_max = safezone
return safe_max
n, m = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(n)] # 연구소 지도 입력
safe = []
for i in range(n):
for j in range(m):
if lab[i][j] == 0:
safe.append((i, j))
# 바이러스가 없는 구역 3개를 뽑아 벽을 세우는 모든 경우의 수
safe = list(combinations(safe, 3)) # 조합 이용
q = deque()
# 바이러스가 있는 지역 모두 큐에 추가
for i in range(n):
for j in range(m):
if lab[i][j] == 2:
q.append((i, j))
print(BFS())