[BOJ] 연구소 - 완전탐색

14502 연구소 골드 5

완전탐색(브루스포스) 문제. 완전탐색을 쓰기 싫어서 고민하다가 시간이 많이 갔는데 완전탐색밖에 방법이 없었다. n, m 이 모두 8 이하니까 최대 8C3 (56) 정돈데 괜히 고민했다. 시간 복잡도 고민하는 것을 습관화해야겠다.

import sys
input = sys.stdin.readline
from collections import deque
from itertools import combinations

nheight, nwidth = list(map(int, input().split()))
board = []
for _ in range(nheight):
    board.append(list(map(int, input().split())))

virus = set()
blank = set()
blocked = set()
for i in range(nheight):
    for j in range(nwidth):
        if board[i][j] == 1:
            blocked.add((i,j))
        elif board[i][j] == 2:
            virus.add((i,j))
        else:
            blank.add((i,j))

def spreadVirus(v):
    visited = set()
    visited.update(v)

    while len(v) > 0:
        a,b = v.pop()
        for i,j in [(a+1,b),(a,b+1),(a-1,b),(a,b-1)]:
            if (i,j) not in visited and 0<= i < nheight and 0 <= j < nwidth and board[i][j] == 0:
                v.add((i,j))
                visited.add((i,j))
    return len(visited)
answer = 0

for l in combinations(blank, 3):
    for (i,j) in l:
        board[i][j] = 1
    n_newvirus = spreadVirus(virus.copy()) - len(virus)
    answer = max(answer, len(blank) - 3 - n_newvirus)
    for (i,j) in l:
        board[i][j] = 0
print(answer)

---

편의를 위해 바이러스와 벽, 빈 칸을 각각 virus, blank, blocked 에 넣어줬다.
spreadVirus 는 virus 를 퍼뜨린 후 바이러스의 수를 return 한다.

for l in combinations(blank, 3):
    for (i,j) in l:
        board[i][j] = 1
    n_newvirus = spreadVirus(virus.copy()) - len(virus)
    answer = max(answer, len(blank) - 3 - n_newvirus)
    for (i,j) in l:
        board[i][j] = 0

모든 blank 의 3가지 combination(새로운 벽 3개를 세우는 조합)에 대하여 안전 영역의 크기를 구한다.