백준 14502 연구소

백준 14502 연구소 문제를 풀어보았습니다.

언어는 python입니다.

from collections import deque
from itertools import combinations
from copy import deepcopy 

N, M = map(int,input().split())
graph = []
virus = []
can_wall = []
for i in range(N):
    graph.append(list(map(int,input().split())))

safe = -3
deq = deque()
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

result = float('inf')

for i in range(N):
  for v in range(M):
    if graph[i][v] == 2:
      virus.append([i, v])
    if graph[i][v] == 0:
      safe+=1
      can_wall.append([i, v])

comb = list(combinations(can_wall,3))


for tup in comb:
  graph_test = deepcopy(graph)
  for i, v in tup:
    graph_test[i][v] = 1
  deq = deque()
  visited = []
  virus_test = 0
  for i, v in virus:
    deq.append([i, v])
  while deq:
    r, c = deq.popleft()
    if [r, c] not in visited:
      for i in range(4):
        new_r, new_c = [r+ dy[i], c+ dx[i]]
        if new_r < 0 or new_r >= N or new_c < 0 or new_c >= M:
          continue
        if graph_test[new_r][new_c] == 0:
          virus_test+= 1
          deq.append([new_r, new_c])
          graph_test[new_r][new_c] = 2
    visited.append([r, c])
  
  result = min(result, virus_test)

print(safe - result)

우선 combinations 을 통해서 벽을 3개 세울 수 있는 모든 경우의 수를 구한 다음

반복문을 통해서 미리 벽을 세우고 bfs로 바이러스들이 전부다 퍼져나갔을 때 추가된 바이러스의 개수를 구합니다.

최종적으로 result에 들어 있는 각 경우의 추가된 바이러스 숫자 중에서 가장 작은 값을 추출하여 안전구역에서 빼주면 정답이 나옵니다.

바이러스가 뻗어나가는 것을 bfs로 구현하는 건 익숙했지만, combinations을 통해서 벽을 미리 세우고 가야한다는 논리는 생각하는데 오래걸렸습니다...

바이러스에 대한 bfs를 하면서 중간 중간 벽을 세우며 최솟값을 추출하려고 했지만 어떤 바이러스를 먼저 뻗어나가게 하는지에 따라서 경우가 달라지기 때문에 해당 알고리즘으로는
해결하지 못했습니다..