popeye0618

Backend Developer

[python] 백준 - 14502 (연구소)

ko 0 조회수

골드4 문제이며, 제한 시간은 2초이다.

문제

해결 과정

우선 바이러스를 전파하는 과정에서는 BFS를 사용하는 것이 효과적이다. BFS를 이용해서 바이러스를 전파하고, 문제를 보면 반드시 벽을 3개 쳐야하는 조건을 가지고있다. 따라서 백트래킹을 이용해서 모든 경우에 대해 벽 3개를 세울 것이다.

아이디어는 어렵지 않았지만 구현이 살짝 헷갈리는 문제였다. 내가 잘 구현하고 있는지가 자꾸 의심이 됐다 ㅋㅋ

풀이

py
from collections import deque
import copy

def bfs():
  global answer
  temp = copy.deepcopy(graph)
  queue = deque()
  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]
  for i in range(n):
    for j in range(m):
      if graph[i][j] == 2:
        queue.append((i, j))

  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < n and 0 <= ny < m and temp[nx][ny] == 0:
        temp[nx][ny] = 2
        queue.append((nx, ny))
        
  cnt = 0
  for i in range(n):
    for j in range(m):
      if temp[i][j] == 0:
        cnt += 1
  answer = max(answer, cnt)

def set_graph(count):
  if count == 3:
    bfs()
    return
  
  for i in range(n):
    for j in range(m):
      if graph[i][j] == 0:
        graph[i][j] = 1
        set_graph(count + 1)
        graph[i][j] = 0

n, m = map(int, input().split())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))

answer = 0
set_graph(0)

print(answer)

여기서 그래프를 temp로 복사해준 이유는 바이러스를 전파시킬 때 방문 여부를 따로 리스트로 만들지 않고, temp를 2로 만들어서 전파시키므로 원본 그래프를 수정하지 않기 위해서이다.

댓글

0

아직 댓글이 없습니다.

댓글 쓰기