[Python] 14502번 연구소

✏️ 문제

 

문제 파악

바이러스가 벽을 제외하고 네 방향으로 퍼질 수 있으므로 bfs를 사용했다. 

그리고 비어있는 영역 중에 3개의 영역에 벽을 세울 수 있으므로 combinations을 사용해야 한다.

for .. in combinations(가능한 위치 배열, 개수)

 

벽을 세운 후에 남아있는 영역 중 안전 영역의 개수를 구해야 하므로 dfs를 돈 결과가 필요하다.

그래서 연구소 배열을 deepcopy를 통해 여러 개의 연구소 배열을 만들고 여러 연구소 배열의 안전 영역의 개수 중 제일 많은 영역을 출력하도록 max를 사용해 코드를 짰다.

 

 

알고리즘

• 구현
• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색

 

코드

import sys
import copy
from collections import deque
from itertools import combinations

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
empty = []
virus = []
max_count = 0

for i in range(n):
  for j in range(m):
    if graph[i][j] == 0:
      empty.append((i, j))
    if graph[i][j] == 2:
      virus.append((i, j))

def dfs(graph, virus):
  q = deque(virus)

  while q:
    x, y = q.popleft()

    for i in range(4):
      dx = x + d[i][0]
      dy = y + d[i][1]

      if 0 <= dx < n and 0 <= dy < m and graph[dx][dy] == 0:
        graph[dx][dy] = 2
        q.append((dx, dy))

def safe(graph):
  count = sum(row.count(0) for row in graph)
  return count

for walls in combinations(empty, 3):
  temp_graph = copy.deepcopy(graph)
  for x, y in walls:
    temp_graph[x][y] = 1

  dfs(temp_graph, virus)
  count = safe(temp_graph)
  max_count = max(count, max_count)

print(max_count)