[BOJ 14502] 연구소(Python)

문제

연구소

문제 해설

구현력이 필요한 문제입니다. 문제에서 요구하는 것은 간단합니다.

1. 벽을 3개 세우세요.
2. 바이러스를 퍼트리고 안전 영역을 검사하세요.

벽을 3개 세우는 것은 벽을 세울 수 있는 영역을 모두 리스트에 넣고 combination 돌렸습니다. 그렇게 3개의 조합이 나오면 벽을 세우고 bfs를 통해 바이러스를 퍼트린 후 전체 영역을 검사하면 됩니다.

저는 deepcopy를 사용해 graph를 복사한뒤 벽을 세우고 바이러스를 퍼트렸습니다. 검사를 하는 것도 전체 영역을 검사하지 않고, 처음 0의 개수를 센 후 바이러스가 하나 퍼질때마다 0의 개수를 차감했습니다. 이렇게하면 바이러스를 퍼트리고 매번 전체 영역을 검사할 필요가 없습니다.

풀이 코드

from itertools import combinations
import copy

n, m = map(int, input().split())
graph = []
blank = []
virus = []
zerocnt = 0
answer = 0
for _ in range(n):
    graph.append(list(map(int, input().split())))

# 벽이 들어설 수 있는 좌표를 저장
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            zerocnt += 1
            blank.append((i, j))
        elif graph[i][j] == 2:
            virus.append((i, j))

# 바이러스를 퍼트린 후 안전 영역 검사
def check(arr, zerocnt):
    # zerocnt = 벽3개 박기전 0의 개수
    q = []
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    # 바이러스 퍼트리기
    # 바이러스를 퍼트리기만 하면 되는거라 que 필요 X
    q += virus
    while q:
        x, y = q.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == 0:
                arr[nx][ny] = 2
                zerocnt -= 1
                q.append((nx, ny))
    return zerocnt - 3


for wall in combinations(blank, 3):
    arr = copy.deepcopy(graph)

    for x, y in wall:
        arr[x][y] = 1
    answer = max(answer, check(arr, zerocnt))
print(answer)