[Python] 백준 17141 연구소 2

1. 문제 - 백준 17141 연구소 2

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

 

💡알고리즘 - BFS, 브루트포스

• 바이러스를 놓을 수 있는 위치에 m개의 바이러스를 넣은 모든 경우의 수 중 바이러스를 퍼뜨릴 수 있는 최소 시간을 반환한다 -> 브루트포스
• 상하좌우 인접한 빈칸으로 복제되며, 바이러스를 퍼뜨리는 최소 시간 -> BFS

from collections import deque
from itertools import combinations
import copy
# 모든 빈 칸에 바이러스를 퍼뜨리는 최소시간 -> BFS
# 바이러스를 놓을 수 있는 칸들에 m개의 바이러스를 놓기 -> 조합, 완전탐색

n, m = map(int, input().split())
board = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]     # 상하좌우 오프셋
viruses = []  # 바이러스 좌표를 저장할 배열
answer = int(1e9)

for i in range(n):
  temp = list(map(int, input().split()))
  board.append(temp)
  for j in range(n):
    if board[i][j] == 2:
      viruses.append((i, j))  # 바이러스 좌표 저장
      board[i][j] = 0
    if board[i][j] == 1:   # 빈칸에 바이러스가 퍼진 시간의 1초와 벽의 1을 구분하기 위해, 벽의 경우 -1로 두기
      board[i][j] = -1

def bfs(virus, board2):
  q = deque(virus)
  visited = [[False] * n for _ in range(n)]
  for x, y in q:    # 시작점의 모든 부분을 방문처리 해야한다.
    visited[x][y] = True
  maxvalue = 0
  
  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<n and not visited[nx][ny] and board2[nx][ny] != -1:    # 벽이 아닌 모든 곳에 바이러스가 퍼질 수 있음
        visited[nx][ny] = True
        board2[nx][ny] = board2[x][y] + 1
        maxvalue = max(maxvalue, board2[nx][ny])  # 바이러스가 퍼지는데 걸리는 시간을 최대값으로 갱신
        q.append((nx, ny))

  # 위에서 모두 탐색을 끝냈음에도 방문하지 않은 빈칸이 남아있을 경우 무한대의 값 return
  for i in range(n):
    for j in range(n):
      if board2[i][j] == 0 and not visited[i][j]:
        return int(1e9)

  return maxvalue

for combi in list(combinations(viruses, m)):
  board2 = copy.deepcopy(board)
  virus = list(combi)
  result = bfs(virus, board2)
  answer = min(answer, result)

# answer가 int(1e9)라는 의미는 어떻게 바이러스를 놓아도 빈칸이 생기는 경우이므로 이 때는 -1을 return함
print(answer if answer != int(1e9) else -1)

 

💡 놓쳤던 부분

바이러스를 m개 놓고 동시다발적으로 바이러스가 퍼진다 -> 즉 시작점이 여러개이므로, 모든 시작점을 방문처리해야한다.