[Python] 백준 17142 연구소3

1. 문제 - 백준 17142 연구소 3 (삼성 SW 역량테스트 기출)

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

 

💡알고리즘 - BFS + 조합

- 연구소에 있는 모든 바이러스들 중, m개를 활성 상태로 변경했을 때의 모든 경우의 수에서 빈칸에 바이러스가 퍼지는 최소 시간 -> 조합
(from itertools import combinations 활용)

- 그래프 + 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간 -> BFS

 

✅ 풀이

from itertools import combinations
from collections import deque
import sys

n, m = map(int, input().split())   # m개의 바이러스를 활성상태로 둘 수 있음
board = []    # nxn 인 연구소
viruses = []
zero_count = 0
for i in range(n):
  board.append(list(map(int, input().split())))
  for j in range(n):
    if board[i][j] == 2:
      viruses.append((i, j))
    if board[i][j] == 0:
      zero_count += 1

if zero_count == 0:  # 빈칸이 아얘 없다면 바이러스가 이미 퍼진 상태이므로 0을 출력하고 종료한다.
  print(0)
  exit()
      
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
INF = sys.maxsize
answer = INF
combi = combinations(viruses, m)   # 바이러스중에 m개를 골라서 퍼뜨리는 모든 경우의 수 조합

def bfs():
  max_time = 0
  zero_count2 = 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 visited[nx][ny] == -1:
        if board[nx][ny] == 0:
          zero_count2 += 1
          q.append((nx, ny))
          visited[nx][ny] = visited[x][y] + 1
          max_time = max(visited[nx][ny], max_time)
        elif board[nx][ny] == 2:
          q.append((nx, ny))
          visited[nx][ny] = visited[x][y] + 1

  if zero_count == zero_count2:
    return max_time
  else:    # 모든 빈칸에 바이러스를 퍼뜨릴 수 없는 경우
    return INF

for c in combi:
  q = deque([])
  visited = [[-1] * n for _ in range(n)]
  for x, y in c:
    q.append((x, y))
    visited[x][y] = 0   # 방문처리 + 바이러스를 옮기는데 걸리는 시간 0으로 초기화
  answer = min(answer, bfs())

if answer == INF:
  print(-1)
else:
  print(answer)

 

1)

from itertools import combinations

n, m = map(int, input().split())   # m개의 바이러스를 활성상태로 둘 수 있음
board = []    # nxn 인 연구소
viruses = []
zero_count = 0
for i in range(n):
  board.append(list(map(int, input().split())))
  for j in range(n):
    if board[i][j] == 2:
      viruses.append((i, j))
    if board[i][j] == 0:
      zero_count += 1

if zero_count == 0:  # 빈칸이 아얘 없다면 바이러스가 이미 퍼진 상태이므로 0을 출력하고 종료한다.
  print(0)
  exit()

combi = combinations(viruses, m)   # 바이러스중에 m개를 골라서 퍼뜨리는 모든 경우의 수 조합

 

- nxn 인 연구소 board를 입력받고, 입력받음과 동시에 바이러스의 좌표를 저장하고, 빈칸의 갯수를 센다.

- 입력받을 때부터 빈칸의 갯수가 0이면, 이미 모든 빈칸에 바이러스가 있는 경우이므로 0을 출력하고 종료시킨다.

- 바이러스들 중 m개의 바이러스를 골라 활성상태를 만들어 퍼뜨리는 모든 경우의 수를 순회하며 바이러스가 퍼지는 시간의 최소값을 구해야하므로, combinations(viruses, m)을 통해 바이러스 조합들의 모든 경우의 수 리스트를 구한다.

 

2)

import sys
INF = sys.maxsize
answer = INF

for c in combi:
  q = deque([])
  visited = [[-1] * n for _ in range(n)]
  for x, y in c:
    q.append((x, y))
    visited[x][y] = 0   # 방문처리 + 바이러스를 옮기는데 걸리는 시간 0으로 초기화
  answer = min(answer, bfs())

if answer == INF:
  print(-1)
else:
  print(answer)

 

- 모든 조합마다 순회하며 BFS를 통해 모든빈칸에 바이러스가 퍼지는 최소 시간을 갱신한다. 이때 최소값을 경우마다 갱신하기 위해
answer를 초기에 무한대의 수로 둔다. (import sys, sys.maxsize)

- 만약에 모든 경우의 수마다 순회했음에도 answer가 무한대의 값이라는 이야기는 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우를 의미하므로, 이때 -1을 출력하고, 그게 아니라면 최소값을 출력한다.

 

3)

def bfs():
  max_time = 0
  zero_count2 = 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 visited[nx][ny] == -1:
        if board[nx][ny] == 0:
          zero_count2 += 1
          q.append((nx, ny))
          visited[nx][ny] = visited[x][y] + 1
          max_time = max(visited[nx][ny], max_time)
        elif board[nx][ny] == 2:
          q.append((nx, ny))
          visited[nx][ny] = visited[x][y] + 1

  if zero_count == zero_count2:
    return max_time
  else:    # 모든 빈칸에 바이러스를 퍼뜨릴 수 없는 경우
    return INF

for c in combi:
  q = deque([])
  visited = [[-1] * n for _ in range(n)]
  for x, y in c:
    q.append((x, y))
    visited[x][y] = 0   # 방문처리 + 바이러스를 옮기는데 걸리는 시간 0으로 초기화
  answer = min(answer, bfs())

 

- BFS 부분이다. 매 조합의 경우의 수마다 visited를 모든 칸이 -1인 2차원 배열로 초기화하고,
활성화할 바이러스 배열이 초기 시작점이므로 deque에 바이러스 좌표들을 모두 넣어준다.

- 이때 활성화된 바이러스는 BFS에서 탐색 대상이 아니므로 반드시 visited[x][y] = 0으로 방문처리를 해주어야한다.

- 문제 조건에 따르면, 활성화된 바이러스는 상하좌우 인접한 칸 중 빈칸 혹은 비활성화된 바이러스가 있는 칸에 퍼질 수 있다.

        if board[nx][ny] == 0:
          zero_count2 += 1
          q.append((nx, ny))
          visited[nx][ny] = visited[x][y] + 1
          max_time = max(visited[nx][ny], max_time)
        elif board[nx][ny] == 2:
          q.append((nx, ny))
          visited[nx][ny] = visited[x][y] + 1

 

- 빈칸인 경우에는 이후에 모든 빈칸에 바이러스를 퍼뜨릴 수 있는지를 따지기 위해서 zero_count2 변수를 통해 빈칸의 갯수를 세주고,
바이러스를 퍼뜨리는 최소 시간을 가져오기 위해 빈칸 위치의 visited 배열 원소값의 최대값을 갱신해준다.
그리고 원래 BFS 방식과 동일하게 최단거리 갱신 및 지날 수 있는 경로에 추가해준다. (q.append((nx, ny))

- 이부분이 실수하기 좋은 부분일것 같은데, 활성화된 바이러스는 비활성화된 바이러스에도 퍼질 수 있다. 따라서 이 경우에도 반드시 방문처리 및 지날 수 있는 경로에 추가해주어야한다.

 

  if zero_count == zero_count2:
    return max_time
  else:    # 모든 빈칸에 바이러스를 퍼뜨릴 수 없는 경우
    return INF

 

- 그리고 마지막에 위에서 센 0의 갯수와 각 BFS마다의 0의 갯수가 동일하다는 의미는 모든 빈칸에 바이러스를 놓을 수 있다는 의미이므로, 차례대로 구한 최대값을 반환해준다. 같지 않으면 빈칸에 바이러스를 퍼뜨릴 수 없다는 의미이므로 최소값을 갱신하지 못하니 INF를 return해준다.