[python] 14502. 연구소

문제 출처

14502. 연구소

 

풀이

초기에 주어진 배열에서 벽이 더이상 추가되지 않는다면 BFS탐색을 통해 바이러스를 퍼뜨린 후, 더이상 바이러스가 퍼지지 않을 때의 빈공간의 갯수를 구하면 된다. 하지만 이 문제는 3개의 벽을 추가로 세워야 하기 때문에 초기 배열에서 빈 공간의 좌표를 파악하고 좌표들 중 3개를 뽑는 조합을 계산한 후 바이러스를 퍼뜨려 안전 영역 크기의 최댓값을 구하면 된다.

 

1. 초기 배열에서 바이러스와 빈 공간의 좌표들을 저장한다.
2. 벽을 추가로 3개 세웠다고 가정했을때의 빈 공간의 갯수를 구하고, 최댓값을 초기화 한다.
3. 빈 공간의 좌표를 기록한 리스트에서 중복되지 않는 3개의 좌표를 뽑는다.
4. 3번에서 구한 조합의 모든 경우에서 같은 작업을 반복해야 하므로 초기의 배열과 바이러스를 저장한 리스트를 복사한다.
5. 복사된 배열에 새로 추가된 벽을 표시하고 바이러스를 BFS 탐색을 통해 퍼뜨린다.
6. 바이러스가 퍼질때마다 2번에서 구한 빈 공간의 갯수를 1 씩 감소한다.
7. 바이러스가 퍼지는 동안 남은 공간의 갯수가 최댓값 이하가 되면 다음 작업으로 넘어간다.
8. 바이러스가 다 퍼진 후 남은 공간의 갯수가 최댓값보다 크면 최댓값을 갱신한다.
9. 4~8번의 작업을 3번에서 구한 모든 경우에서 똑같이 반복한다.

 

from itertools import combinations
from copy import deepcopy

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

viruses = []
empties = []
for y in range(N):
    for x in range(M):
        if arr[y][x] == 2:
            viruses.append((x, y))
        elif arr[y][x] == 0:
            empties.append((x, y))

cnt_zeros = len(empties) - 3
max_ = 0
def spread(viruses, walls):
    global max_, cnt_zeros

    left = cnt_zeros
    brr = deepcopy(arr)

    q = viruses[::]
    for x, y in walls:
        brr[y][x] = 1

    while q:
        x, y = q.pop(0)
        for dx, dy in (0, -1), (1, 0), (0, 1), (-1, 0):
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= M or ny < 0 or ny >= N:
                continue
            if brr[ny][nx]:
                continue
            left -= 1
            brr[ny][nx] = 2
            q.append((nx, ny))

        if left <= max_:
            return

    max_ = left

for idx, walls in enumerate(combinations(empties, 3)):
    spread(viruses, walls)

print(max_)