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)
'알고리즘 > 삼성' 카테고리의 다른 글
[백준-실버2] 14889번 스타트와 링크 (완전탐색, 파이썬) (0) | 2022.02.07 |
---|---|
[백준 -실버1] 14888번 연산자 끼워넣기(완전탐색, 파이썬) (0) | 2022.02.07 |
[백준 -실버1] 14891번 톱니바퀴(구현, 파이썬) (0) | 2022.02.05 |
[백준 -골드5] 15686번 치킨 배달(완전탐색, 파이썬) (0) | 2022.02.04 |
[백준 -골드5] 14503번 로봇 청소기(구현, 파이썬) (0) | 2022.02.04 |