[python] BOJ 백준 14502: 연구소

1. 문제  

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.  0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다. 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

2. 입력   

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

3. 출력   

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

4. 해결방법   

BFS알고리즘을 통해 바이러스를 전파시키고, itertools를 통해 벽을 세울 수 있는 모든 조합을 구하는 브루트포스 문제이다. 다만, 삼성 코딩테스트 실전에서는 itertools 라이브러리를 사용하지 못하기 떄문에 이에 대해서는 대비가 필요하다.  

1) virus 함수: 바이러스가 있는 모든 칸은 큐에 저장한 다음, 큐에서 하나씩 빼면서 상하좌우를 탐색하며 바이러스가 퍼지지 않은 빈칸이면 큐에 저장해준다. 간단한 BFS 알고리즘이다. 

2) 메인함수에서는 입력을 받은 뒤, 빈칸의 인덱스를 모두 저장해 주었다. 빈칸은 벽을 세울 수 있는 후보군이기 때문에 여기서 3개를 골라 조합을 만들어야한다. 만든 조합에 대해서 위에서 만든 virus함수를 통해 퍼질수 있는 빈칸의 수를 저장한다. 정답 후보군 중에서 가장 최소값을 구해야 안전영역의 최대크기를 구할 수 있으므로 총 빈칸값에서 바이러스가 퍼진 최소값을 빼준다. 여기서 벽의 수 3도 빼주어야 정확한 수가 나온다. 

 

5) 구현코드       

import itertools
from collections import deque
import copy


dy=[0,0,1,-1]
dx=[1,-1,0,0]

#바이러스 퍼지는 함수 
def virus(n,m,graph): 
  result=0
  queue = deque() #bfs
  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 k in range(4): #상하좌우에 대해 
      ix=dx[k]
      iy=dy[k]
      if 0<=x+ix<n and 0<=y+iy<m: #연구소 칸이고
        if graph[ix+x][y+iy]==0: #바이러스가 퍼지지 않은 빈칸이면 
          graph[x+ix][y+iy]=2 #바이러스 퍼짐
          queue.append([ix+x,iy+y]) #큐에 저장 
          result+=1 #바이러스 퍼진 칸의수 증가 
  return result
  

n,m=map(int,(input().split()))
graph=[list(map(int, input().split())) for _ in range(n)]
answer=[]
zero=[] #빈칸 배열

for i in range(n):
  for j in range(m):
    if graph[i][j]==0:
      zero.append([i,j]) #빈칸의 인덱스 저장 
zeroNum=len(zero) #빈칸의 개수 
wall=list(itertools.combinations(zero,3)) #세울수 있는 벽의 모든 조합
for w in wall: #모든 조합에 대해서 
  graphCopy=copy.deepcopy(graph)
  for i in w:
    graphCopy[i[0]][i[1]]=1 #벽을 세우고 
  temp=virus(n,m,graphCopy) #바이러스 퍼지기 
  answer.append(temp) #바이러스가 퍼진 칸의 수 저장 


print(zeroNum-min(answer)-3) #빈칸 - 바이러스가 퍼진칸의 수 - 벽의 수

 

⭐️난이도:  골드5⭐️ 

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

14502번: 연구소