14502번: 연구소

[amm0124]

문제

백준 14502번을 풀었습니다.
백준 14502 : https://www.acmicpc.net/problem/14502

설명

바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 합니다. 빈 공간은 0, 벽은 1, 바이러스는 2라고 할 때, 벽 3개를 빈 공간에 잘 세워서 바이러스 확산 영역을 최소화하는 문제입니다.

접근법

그래프를 빙자한 브루트포스 문제입니다. 연구소의 크기 N,M이 8 이하입니다. 즉 빈 공간이 많아봤자 64개(N*M)입니다. 64개에서 3개를 뽑는 경우의 수(벽을 세울 후보자들의 경우의 수)는 많아봤자 41664개입니다.

바이러스를 확산시키는 방식은 dfs, bfs 둘 다 사용해도 괜찮은데, 저는 bfs를 사용했습니다. 왜냐하면 퍼진 바이러스가 주변을 감염시킨 후, 다음 단계로 넘어가는 방식이라서 bfs를 사용했습니다.

즉, 41664의 경우의 수에 대하여 64번의 연산 (완전탐색 - 브루트포스)를 하는 것과 똑같은 결과입니다. 64C3 * 64 의 연산을 처리하는데 2초는 충분합니다!

소스 코드

import sys 
from collections import deque
from copy import deepcopy

n,m = map(int, sys.stdin.readline().split())
lab = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

candidate = list(filter(lambda x: lab[x[0]][x[1]] == 0, [(i, j) for i in range(n) for j in range(m)]))
virus = list(filter(lambda x: lab[x[0]][x[1]] == 2, [(i, j) for i in range(n) for j in range(m)]))

answer = 0  

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

len_ = len(candidate)

for i in range(len_) :
    for j in range(i+1, len_) :
        for k in range(j+1, len_) :
    
            lab_ = deepcopy(lab)
            
            lab_[candidate[i][0]][candidate[i][1]] = 1 
            lab_[candidate[j][0]][candidate[j][1]] = 1 
            lab_[candidate[k][0]][candidate[k][1]] = 1 
            queue = deque(virus)
            
            while queue :
                top = queue.popleft()
                now_x, now_y = top[0], top[1]
                lab_[now_x][now_y] = 2
                for _ in range(4) : 
                    next_x = now_x + dx[_]
                    next_y = now_y + dy[_]
                    if 0 <= next_x < n and 0 <= next_y < m and lab_[next_x][next_y] == 0:
                        lab_[next_x][next_y] = 2
                        queue.append((next_x, next_y))
            
            temp = sum(row.count(0) for row in lab_)
            answer = max(answer, temp)
print(answer)

마무리하며

오랜만에 구현 + 탐색 + 시뮬레이션 문제를 풀었습니다. 시뮬레이션 문제는 역시 ~ 현실과 비슷하게 ~