[백준]14502_연구소

문제

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

풀이

• 해당 문제는 모든 가능성에 대해 bfs()로 안전 구역을 구하고 안전 구역 개수의 최대값을 구할 수 밖에 없다.
• 따라서 완전탐색을 했다.
• 벽이 될 수 있는 가능성은 조합을 사용했다.
• 모든 경우의 수에 대해 그래프가 초기화되어야 하므로 슬라이싱을 활용한 깊은 복사를 사용했다.

코드

# 입력 받으며 동시에 데이터 정리
import sys
from itertools import combinations
from collections import deque
n, m = map(int, sys.stdin.readline().strip().split(" "))
graph = []
for _ in range(n):
  graph.append(list(map(int, sys.stdin.readline().strip().split(" "))))
 
# 그래프를 돌며 벽의 위치와 바이러스 위치 모아두기
zero_locate = []
virus_locate = []
for y in range(n):
  for x in range(m):
    if graph[y][x] == 0:
      zero_locate.append([y,x])
    elif graph[y][x] == 2:
      virus_locate.append([y,x])
      
# itertools.combinations를 사용하여 쉽게 모든 경우의 수 구하기
candidates = combinations(zero_locate, 3)

# bfs를 통해 바이러스 증식 후의 그래프를 만들고 안전구역 세기
def bfs(graph):
  queue = deque(virus_locate)
  dy = [0, 1,0,-1]
  dx = [1,0,-1,0]
  while queue:
    cy, cx = queue.popleft()
    for i in range(4):
      ny, nx = cy + dy[i], cx +dx[i]
      if 0<= ny < n and 0 <= nx < m and graph[ny][nx] == 0:
        graph[ny][nx] = 2
        queue.append([ny,nx])
  count = 0
  for y in range(n):
    for x in range(m):
      if graph[y][x] == 0:
        count += 1
  return count
    
# 안전구역 개수의 최대값 구하고 return  
safe_zone = 0
for candidate in candidates:
  g = [[graph[y][x] for x in range(m)] for y in range(n)]
  for y,x in candidate:
    g[y][x] = 1
  if bfs(g) > safe_zone:
    safe_zone = bfs(g)
print(safe_zone)