백준: 14502 연구소

연구소 시리즈

• 연구소
• 연구소 2
• 연구소 3

 

문제

14502번: 연구소

 

문제 풀이

 연구실에 바이러스가 유출되었고, 벽을 3개 설치할 수 있을 때 가장 많은 안전지대를 확보한 경우를 찾는 문제이다. 문제를 풀기 위해서는 FloodFill과 같이 바이러스가 있는 지점으로부터 상, 하, 좌, 우로 전파가 가능한지 확인하여 바이러스가 전파될 것이다. 토마토 문제와 유사하지만 다른 점은 벽을 세워야 한다는 것이다. 따라서 다음과 같은 경우의 수를 구하여 문제를 해결 할 수 있다.

 

• 백트랙킹을 통해 3개의 벽을 세우는 모든 경우의 수를 찾는다.
• 각 경우의 수마다, 바이러스를 전파시키고 안전 지역의 수를 계산한다.

 

코드

from sys import stdin
from collections import deque
from copy import deepcopy


def visitable(x, y, set_wall):
    return 0 <= x < n and 0 <= y < m and not set_wall[x][y]


def bfs():
    set_wall = deepcopy(graph)
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    q = deque()

    for x in range(n):
        for y in range(m):
            if set_wall[x][y] == 2:
                q.append([x, y])

    while q:
        cur_x, cur_y = q.popleft()
        for x, y in dirs:
            next_x, next_y = cur_x + x, cur_y + y
            if visitable(next_x, next_y, set_wall):
                set_wall[next_x][next_y] = 2
                q.append([next_x, next_y])

    cnt = 0
    for is_virus in set_wall:
        cnt += is_virus.count(0)

    return cnt


def dfs(select):
    global answer

    if select == 3:
        answer = max(answer, bfs())
        return

    for x in range(n):
        for y in range(m):
            if not graph[x][y]:
                graph[x][y] = 1
                dfs(select + 1)
                graph[x][y] = 0


if __name__ == '__main__':
    answer = 0
    n, m = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
    dfs(0)
    print(answer)

 느린 파이썬으로는 시간 초내에 통과할 수 없다. 따라서 PyPy3로 제출하여야 한다.