[백준] 14502번 연구소 - 파이썬

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

 

풀이

N: 지도의 세로 크기, M: 지도의 가로 크기, 지도좌표 값(바이러스(2), 벽(1))

실버문제들 중에서도 흔히 볼 수 있는 바이러스나, 토마토 문제처럼 특정한 값을 가진 칸에 인접한 칸들에게 영향을 주는 문제이다. 나는 이런 문제가 나올 때마다 BFS를 써준다. 다만 이 문제가 껄끄러운 이유는 벽을 어떻게 세워야 최대안전영역이 나오는가이다. 따라서 우리는 벽을 세울 수 있는 모든 경우의 수를 구해서 BFS에 돌린 뒤 나올 수 있는 안전영역의 개수를 모두 구할 것이다.  

 

1, 입력값을 받아준다.

2, 2차원 배열 안에 들어가 있는 바이러스(2)의 좌표 값(가로: x, 세로: y)을 찾아내어 deque에 넣어준다.

3, 벽을 선택하는 함수를 재귀함수를 통해 만들어준다.

4, 벽을 선택해서 2차원 배열에 저장해준 뒤 BFS를 실행해준다.

5, 이를 반복해서 벽이 세워지는 모든 경우의 2차원 배열을 BFS를 돌려준 뒤에 최대값을 구해준다.

 

# 14502번 연구소
# 벽 3개를 세워서 바이러스가 최대로 안퍼지게하고 안전영역의 최댓값을 구하기
# 바이러스는 상하좌우로 퍼진다. N = 세로, M = 가로
import sys, copy
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
max_result = 0

for _ in range(N):
    graph.append(list(map(int, input().split())))

def bfs():
    queue = deque()
    global max_result
    test = copy.deepcopy(graph)
    for y in range(N):
        for x in range(M):
            if test[y][x] == 2:
                queue.append((x, y))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < M and 0 <= ny < N:
                if test[ny][nx] == 0:
                    test[ny][nx] = 2
                    queue.append((nx, ny))
    result = 0
    for y in range(N):
        for x in range(M):
            if test[y][x] == 0:
                result += 1
    max_result = max(max_result, result) 

def wall(cnt):      # 벽을 완전탐색으로 골라내는 함수
    if cnt == 3:
        bfs()
        return
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                graph[i][j] = 1
                wall(cnt+1)
                graph[i][j] = 0

wall(0)
print(max_result)