[백준] 연구소

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

14502번: 연구소

구현과, bfs 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

다음과 같이 연구소가 있는데, 0,1,2는 각각 빈 칸, 벽, 바이러스를 나타냅니다. 이곳의 빈 칸중 세군데에 벽을 추가로 설치하여 바이러스가 퍼지지 않은 방의 갯수를 최대로 만드는 것이 문제입니다. 

 

<Solution>

좋은 방법이 없을지 생각을 해보았는데,

빈 칸(0) 중 3개를 뽑아서 1로 만들고 2(바이러스) 를 퍼트리고, 빈 칸의 갯수를 세는 것 말고는 딱히 괜찮은 방법이 생각나지 않았습니다. 

 

이렇게 구현하면, 시간 복잡도가 많이 나올것 같아서 대략 계산을 해보면, 연구소의 크기가 N*M인데 (3<= N, M <= 8)의 조건이 주어지므로 최대 64칸 인 것을 알 수 있습니다.

넉넉잡아서 64칸중 3칸을 뽑는 가짓수 만큼의 경우의 수를 생각 해보면, 64C3 = 41664로 좋지는 않지만 시간초과가 나지는 않을 것 같음을 알 수 있습니다.

 

따라서, 그대로 구현을 하였습니다. 실제 구현은 아래와 같습니다. 

import sys
import itertools
import copy
from collections import deque
N, M = list(map(int, sys.stdin.readline().rstrip().split()))

graph = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]

zero_array = []
two_array = []
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            zero_array.append((i,j))
        if graph[i][j] == 2:
            two_array.append((i,j))

nCr = itertools.combinations(zero_array, 3)
move_r = [0,0,-1,1] # left right up down
move_c = [-1,1,0,0]

max_safe = -1
for nCr_ in nCr:
    cnt = 0
    graph_ = copy.deepcopy(graph)

    graph_[nCr_[0][0]][nCr_[0][1]] = 1
    graph_[nCr_[1][0]][nCr_[1][1]] = 1
    graph_[nCr_[2][0]][nCr_[2][1]] = 1

    # bfs for every 2
    for e in two_array:
        q = deque([e])
        
        while(q):
            r,c = q.popleft()

            for i in range(4):
                new_r = r + move_r[i]
                new_c = c + move_c[i]

                if 0 <= new_r < N and 0 <= new_c < M and graph_[new_r][new_c] == 0:
                    graph_[new_r][new_c] = 2
                    q.append((new_r,new_c))
    
    for p in range(N):
        for q in range(M):
            if graph_[p][q] == 0:
                cnt+=1 
    
    max_safe = max(max_safe, cnt)

print(max_safe)