백준 14502번 : 연구소

https://www.acmicpc.net/problem/14502

14502번: 연구소

문제 상황이 요즘 시국과 비슷해서 나름 몰입해서 풀었다.

 

 연구소 내부는 1x1 칸으로 나눠져있고 각 칸은 빈 칸, 벽, 바이러스 중 하나로 이뤄져있다. 바이러스는 놔두면 상하좌우 인접한 칸으로 증식하면서 빈 칸을 바이러스로 감염시킨다. 하지만 벽이 있는 곳은 이동하지 못하기 때문에 벽을 3개 세워서 바이러스의 증식을 막아야한다.

단, 벽은 반드시 3개를 세워야 하기 때문에 연구소 내부에는 빈 칸이 최소 3칸 존재한다. 벽을 적절히 세워서 최대한 많은 수의 빈 칸(안전지대)을 확보해야한다.

 

 빈 칸을 최대한 확보해야 한다는 것은 바이러스가 최소한으로 이동해야 한다는 것이다. 바이러스의 움직임을 빈 칸만 방문하는 BFS 탐색으로 구현하기로 했다. 방문할때마다 칸의 개수를 세어서 탐색이 끝나면 감염시킨 총 빈 칸의 개수를 리턴하도록 구현했다. 3개의 벽을 어떻게 세우느냐에 따라 그 수가 달라질 것이고 모든 경우의 수 중에서 가장 최소인 값을 구하면 될 것이다.

 

 BFS함수를 구하면서 주의해야할 점은, 리스트 자료형을 함수의 매개 변수로 받을 경우 (원소)값이 아니라 주소값이 복사되기 때문에 매개 변수로 받은 리스트의 원소를 함수 안에서 수정하면 함수 바깥에서 인자로 건네준 리스트의 원소가 변하게 된다. 이를 얕은 복사라고 한다. 이러한 문제는 함수에 인자로 건네줄때 주소값이 다른 리스트를 건네주어 해결할 수 있다. 그런데 이상하게 슬라이싱, 리스트 변환 메소드, 리스트의 copy 메소드를 사용해도 주소값은 다르지만 계속 얕은 복사가 되는 문제가 발생했다. 따라서 copy.deepcopy 메소드를 사용하여 해결했다.

 

 그렇다면 3개의 벽을 세우는 경우의 수를 어떻게 구현할까? itertools 라이브러리에 있는 combinations(조합)을 사용하기로 했다.

솔직히 얘기하면 머릿속에 이 방법밖에 떠오르지 않았다. 과연 제한 시간내에 가능할지 긴가민가 했지만 연산시간을 계산해보니 최악의 경우 반복 횟수가 약 600만번으로 충분히 가능했다. 바이러스와 빈 칸의 좌표를 각각 다른 리스트에 담고 빈 칸들 중에서 임의로 3개를 조합했다. 각 조합마다 BFS탐색을 통해 바이러스가 감염시킨 칸의 개수를 계산해서 가장 작은 값을 구했다.

 

따라서 최종적으로 (총 빈 칸의 개수) - (벽 3개) - (최소 감염 값)을 계산해주면 답을 구할 수 있다.   

너무 단순하게 풀기도 했고 반복이 너무 많아서 걱정했지만, 다행히 이러한 방식으로도 풀 수 있는 문제였다.

(실제 온라인 저지에서는 반복에 강한 pypy로 제출했다.)

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

def bfs(l,w,v):
    queue = deque(v)
    visit = [[False]*m for _ in range(n)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]

    for x, y in w:
        l[x][y] = 1

    cnt = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            px, py = x+dx[i], y+dy[i]
            if px < 0 or px > n-1 or py < 0 or py > m-1:
                continue
            if l[px][py] == 0 and not visit[px][py]:
                queue.append((px, py))
                visit[px][py] = True
                cnt += 1
    return cnt


n, m = map(int, input().split())
lab, virus, space, c = [], [], [], 0
for i in range(n):
    lab.append(list(map(int, input().split())))
    for j in range(m):
        if lab[i][j] == 2:
            virus.append((i,j))
            continue
        elif lab[i][j] == 0:
            space.append((i,j))

com = combinations(space,3)
min_c = 64
for i in com:
    c = bfs(copy.deepcopy(lab), i, virus)
    if min_c > c:
        min_c = c

print(len(space)-3-min_c)