Q16. 연구소
🐣문제
연구소는 크기가 NXM인 직사각형으로 나타낼 수 있으며, 직사각형은 1X1 크기의 정사각형으로 나누어져 있습니다. 연구소는 빈칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지합니다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈칸으로 모두 퍼져나갈 수 있습니다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 합니다.
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
백준 링크 | https://www.acmicpc.net/problem/14502
🐥풀이
일단, 무지성으로 연구실 이차원 배열 만들어서 for문으로 하나씩 돌려보면서 번식시키고 판단하면 무조건! 시간초과로 터진다.. ㅇㅅㅇ.. 그럼 어떻게 해야 할까?
스터디에서 나름 문제를 꽤 풀어보면서 탐색, 특히 DFS는 이차원 배열 만들어서 하나씩 타고 들어가고 탐색하면 99.9% 터지더라 ㅠㅠ 이 때 쓸 수 있는게 큐!!!!
특히나 번식 문제가 나오면 큐에 번식하는 대상의 위치를 담아두고 pop으로 꺼내가면서 판단하면 꽤 효율적인 코드를 짤 수 있었다 ㅎㅅㅎ
그럼 바로 문제에 적용해보자!
1. 먼저 주목할 점은 벽을 3개 세운다. 그러면 2*3=6.
6중 for문으로 빈칸인 곳에 벽을 3개 세우는 모든 경우의 안전영역을 구하고, 가능한 안전영역 중 최솟값을 구하면 된다 :)
2. 안전영역은 어떻게 구할 수 있을까?
연구실 배열을 하나씩 돌면서 바이러스가 있으면 인접한 상하좌우의 빈칸으로 번식시킨다. 모두 번식시킨 후, 다시 연구실을 돌면서 빈칸(0)의 개수를 구하면 안전영역을 구할 수 있다 :)
3. 진짜진짜 마지막! 번식은 어떻게 시키나료?-?
여기서 BFS 알고리즘과 queue를 활용하면 된다!! 2번에서 안전영역을 구하면서 바이러스가 발견되면 바이러스의 위치를 인자로 들고 온다. 위치를 queue에 넣어버리고, 상하좌우 위치 값을 확인하면서 빈칸이면 연구실 배열의 해당 위치에 2로 값을 넣어준다. 번식했으니 queue에도 해당 위치 인덱스를 넣어주면 끝!
정리!
벽 3개 세운다 -> 번식 시킨다 -> 안전영역 구한다 -> 최솟값 구한다
🐓코드
from collections import deque
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dist = [[1,0], [-1,0], [0,1], [0,-1]]
# bfs
def extending(x,y,temp):
queue = deque()
queue.append([x,y])
while queue:
a, b = queue.pop()
for d in dist:
dx, dy = a+d[0], b+d[1]
if 0<=dx<n and 0<=dy<m:
# 연구실 내부이고 빈 곳이면 번식
if temp[dx][dy]==0:
temp[dx][dy]=2
queue.append([dx,dy])
return temp
def checking(board):
temp, count = [[0]*m for _ in range(n)], 0
# 연구실 복제 (0: 빈칸, 1: 벽, 2: 바이러스)
for i in range(n):
for j in range(m):
temp[i][j] = board[i][j]
# 바이러스 번식
for i in range(n):
for j in range(m):
if temp[i][j]==2:
temp = extending(i,j,temp)
# 안전구역(0) 개수
for t in temp:
count += t.count(0)
return count
result = 0
for i1 in range(n):
for j1 in range(m):
if board[i1][j1]!=0:
continue
board[i1][j1] = 1 # 벽1 세우기
for i2 in range(n):
for j2 in range(m):
if board[i2][j2]!=0:
continue
board[i2][j2] = 1 # 벽2 세우기
for i3 in range(n):
for j3 in range(m):
if board[i3][j3]!=0:
continue
board[i3][j3] = 1 # 벽3 세우기
result = max(result, checking(board)) # 안전구역 체크
board[i3][j3] = 0 # 벽3 치우기
board[i2][j2] = 0 # 벽2 치우기
board[i1][j1] = 0 # 벽1 치우기
print(result)
⭐2022.04.12
아직 DFS가 안 익숙했을 때라서 무식하게 배열 하나하나 다 돌려보고 계속 터뜨리고 왜 안되징 ㅠㅅㅠ 하다가 큐로 해결 >_0 뿌듯했다 ㅎㅎㅎㅎ
