https://www.acmicpc.net/problem/14502
최종 목표: 안전 영역의 최대 크기를 출력
위와 같은 문제는 어떻게 쉬운 문제로 쪼갤 수 있을까?🤔
1.벽 3개 임의로 배치
2. 바이러스가 퍼지는 것을 BFS로 구현
3. 1과 2를 수행한 후에 지도 상에 존재하는 0의 개수 세기
4. 1~3 반복해서 0이 가장 많은 결과(안전 영역의 최대 크기) 출력
우선 이렇게 4개의 작은 문제로 쪼개서 생각해보았다.
모든 경우를 시도하여 안전 영역의 최대 크기를 찾아보자
모든 경우의 수 계산
다만, 구현하기 까다로워서 연습이 필요하다.
from collections import deque
n, m = map(int, input().split())
data = [list(map(int, input().split())) for i in range(n)]
temps = [[0] * m for _ in range(n)]
# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0
def walls_dfs(num_walls):
global answer
# 벽 3개 배치
if num_walls == 3:
for i in range(n):
for j in range(m):
temps[i][j] = data[i][j]
# 바이러스 전파
for i in range(n):
for j in range(m):
if temps[i][j] == 2:
virus_bfs(i, j)
# 안전영역 계산
answer = max(answer, get_score())
return
# 빈 공간에 울타리 설치
for i in range(n):
for j in range(m):
if data[i][j] == 0:
data[i][j] = 1
num_walls += 1
walls_dfs(num_walls)
data[i][j] = 0
num_walls -= 1
def virus_bfs(x, y):
queue = deque([(x, y)])
# 현재노드 방문처리
temps[x][y] = 2
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):
# 방문하지 않은 경우
if temps[nx][ny] == 0:
temps[nx][ny] = 2
queue.append((nx, ny))
def get_score():
score = 0
for i in range(n):
for j in range(m):
if temps[i][j] == 0:
score += 1
return score
walls_dfs(0)
print(answer)