백준 알고리즘 14502: 연구소(Python)

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

14502번: 연구소

문제

문제 해결을 위한 과정

이 문제의 경우 조건을 보면 8 x 8로 크기가 제한이 되어있는 것을 알 수 있습니다. 또한 3가지의 벽을 세우는 경우 이므로 64가지의 경우에서 순서에 상관없이 3을 뽑는 즉 64C3이기 때문에 완전 탐색으로 해결해야 함을 알 수 있습니다. 따라서 그래프를 입력받을 때 바이러스인 좌표를 저장하는 리스트와 빈칸을 저장하는 리스트를 각각 만든 후 빈칸의 영역에서 combinations을 사용하여 3개의 구역에 벽을 세운 후 BFS를 이용하여 문제를 해결합니다.

---

문제 해결을 위한 팁

조합을 이용해 3가지 구역에 대해서 벽을 세운 후 BFS를 수행한 후 다시 벽을 없애주어야 합니다. 그래야 다른 지역에 벽을 세울 수 있기 때문입니다.

---

소스코드

 

from itertools import combinations
from collections import deque
import copy
 
N, M = map(int, input().split())
graph = []
blank = []
virus = []
 
for i in range(N):
  graph.append(list(map(int, input().split())))
  for j in range(M):
    if graph[i][j] == 0:
      blank.append((i, j))
    elif graph[i][j] == 2:
      virus.append((i, j))
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def bfs():
  testgraph = copy.deepcopy(graph)
  q = deque(virus)
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < N and 0 <= ny < M:
          if testgraph[nx][ny] == 0:
            testgraph[nx][ny] = 2
            q.append((nx, ny))
 
  count = 0
  for i in range(N):
    for j in range(M):
      if testgraph[i][j] == 0:
        count += 1
  
  return count
 
 
answer = 0
for data in combinations(blank, 3):
  for x, y in data:
    graph[x][y] = 1
  answer = max(answer, bfs())
  for x, y in data:
    graph[x][y] = 0
 
print(answer)