[baekjoon] 14502. 연구소

---

로직

 벽이 추가로 세워질 수 있는 곳에 벽을 세우면서 진행한다. 세울 때마다 기존의 board판에 추가해야하며, 세우고나서 바이러스들이 이동한다. 바이러스 이동하는 것을 move라는 함수를 만들어 매번 사용한다.

 이때, 안전한 공간 갯수는 처음에 0인 값들을 cnt에 다 넣고, 벽이 3개가 추가되니까 cnt - 3하고, 바이러스가 이동한 공간의 갯수를 빼준다(바이러스 이동 공간갯수는 move함수에서 return한다.)

 

코드

from collections import deque
from itertools import combinations
from copy import deepcopy

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


can_wall = []
# virus = deque([])
virus = []
cnt = 0
for i in range(N):
    for j in range(M):
        if board[i][j] == 0:
            can_wall.append([i, j])
            cnt += 1
        elif board[i][j] == 2:
            virus.append([i, j])

def move(virus):
    answer = 0
    virus = virus[:]
    near = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    while virus:
        # x, y = virus.popleft()
        x, y = virus.pop(0)

        for a, b in near:
            xi, yi = x + a, y + b
            if 0 <= xi < N and 0 <= yi < M:
                if bd[xi][yi] == 0:
                    virus.append([xi, yi])
                    answer += 1
                    bd[xi][yi] = 2

    return answer

walls = list(combinations(can_wall, 3))

mymax = 0
for i in walls:
    bd = deepcopy(board)
    for j in range(3):
        a = i[j][0]
        b = i[j][1]
        bd[a][b] = 1
    result = cnt - 3 - move(virus)

    if mymax < result:
        mymax = result

print(mymax)

 

주의할 점

1. virus = virus[:] 이 줄 필수!! why? 함수 돌릴 때마다 바이러스가 있는거를 써야하니까 새로운 virus가 필요함

   -> 처음 값 복사 필요

 

2. virus = virus[:] 하고 while돌면서 virus를 pop해야하는데,

     1) deque하면 TypeError: sequence index must be integer, not 'slice'

     2) 그냥 []하고 pop하면 돌아간다