본문 바로가기
알고리즘/삼성

[백준 -골드5] 14502번 연구소(BFS, 완전탐색, 파이썬)

by 호리미 2022. 2. 4.

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

 

14502번: 연구소

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

www.acmicpc.net

 

 

<복습 체크>

22/02/07                  
O                  

 

<내 코드>

- 우선 벽3개를 세울 수 있는 경우의 수 만큼 확인을 해야해서 시간복잡도를 고려해보았다.

  (64개 중 3개 선택 = (64*63*62)/3! = 41,664 조합을 사용해도 된다고 판단하였다.)

- 그리고 원본 리스트가 변경되면 안되기 때문에 deepcopy를 이용해서 깊은 복사를 하였다.

- 나머지는 주석으로 설명해놓음

from itertools import combinations
from collections import deque
import sys
import copy
input = sys.stdin.readline

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

#빈 공간의 좌표를 담아줌
#빈 공간에 벽을 세울수 있기 때문
empty = []
for i in range(n):
    for j in range(m):
        if lab[i][j] == 0:
            empty.append([i,j])

#벽을 3개 세울수 있으므로 조합을 이용해서 3개를 뽑는 경우를 리스트에 담음
wall_list = list(combinations(empty, 3))

#bfs 함수 구현
dx = [1, -1, 0, 0]
dy = [0 ,0 ,1, -1]
def bfs(x,y): # 메인에서 2일때 bfs 호출
    queue = deque()
    queue.append([x,y])
    
    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:
                if lab_copy[nx][ny] ==0:
                    lab_copy[nx][ny] = 2 #바이러스 전파
                    queue.append([nx,ny])
                    
max_safe = 0
#벽을 세울 수 있는 경우의 수만큼 반복
for w in wall_list:
    
    #벽세우기
    lab_copy = copy.deepcopy(lab) #원본 유지위해 deepcopy  
    for i in range(3):
        x_pos, y_pos = w[i][0], w[i][1]
        lab_copy[x_pos][y_pos] = 1 
        
    # bfs 호출로 바이러스 전파
    for i in range(n):
        for j in range(m):
            if lab_copy[i][j] ==2 :#연구실에 바이러스가 있을 때 전파
                bfs(i,j)
            
    #연구실에서 0을 갯수 찾기
    #최댓값을 찾아야하므로 max_safe 업데이트
    temp = 0
    for i in range(n):
        for j in range(m):
            if lab_copy[i][j] ==0:
                temp +=1
    max_safe = max(max_safe, temp)
                
print(max_safe)