✅ Coding Test
🎈 14502 연구소
바이러스의 확산을 막기 위해 주어진 NxM 크기의 연구소 내 벽을 세우려고 한다.
0은 빈칸, 1은 벽, 2는 바이러스가 있을 때 바이러스는 인접한 4방향으로 모두 퍼져나갈 수 있어 벽 3개를 세워 바이러스가 퍼질 수 없는 안정 영역을 만들어야 한다.
최종적으로 정리를 하면 연구소의 크기와 현재 연구소 상태 (빈칸, 벽, 바이러스)가 주어지고 벽 3개를 세울 수 있을 때 얻을 수 있는 안전 영역의 최대 크기를 구하는 문제.
from collections import deque
import sys, copy
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 제출용 정답
answer = 0
# 안전영역 최대 크기 계산
def safe_zone(board):
global answer
cnt = 0
for i in range(n):
for j in range(m):
if board[i][j] == 0:
cnt += 1
answer = max(answer, cnt)
return answer
# BFS로 탐색 (바이러스인 경우 퍼질 수 있게)
def bfs():
tmp = copy.deepcopy(graph)
queue = deque()
# 현재 위치가 바이러스인 경우에만 퍼지므로 queue에 넣기
for i in range(n):
for j in range(m):
if tmp[i][j] == 2:
queue.append((i, j))
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 tmp[nx][ny] == 0:
tmp[nx][ny] = 2
queue.append((nx, ny))
safe_zone(tmp)
return
# 벽 3개 만드는 함수.
def three_walls(wall_cnt):
if wall_cnt == 3:
bfs()
return
else:
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
graph[i][j] = 1
three_walls(wall_cnt + 1)
graph[i][j] = 0
three_walls(0)
print(answer)< 해설 >
해당 문제를 푸는데 있어 핵심은 벽을 3개나 더 세워야 하는 것. 벽을 다 세우고 나서 바이러스를 퍼뜨리는 것. 바이러스가 다 퍼지고 난 이후 안전 영역 개수를 구하는 것이다.
따라서 이를 전부 함수화해 구현하였다.
순서대로 보면 다음과 같다.
- BFS를 활용해 진행한 풀이로 연구소의 가로/세로/그래프 상태를 입력값으로 받고 안전 영역 크기인 answer, 방향을 위해 dx, dy를 입력받는다.
- 안전 영역의 크기를 구하는 함수인 safe_zone을 만들어 그래프를 입력받으면 현재 그래프 내 0의 개수를 리턴한다.
- 바이러스가 퍼지는 과정을 BFS로 구현했고 벽을 만들고 지우고 하는 과정을 반복해주기 위해 BFS함수 내 tmp라는 deepcopy문으로 graph를 복사한다. 이후 현재 위치에 바이러스가 존재하면 탐색을 시작하는 방식으로 진행하고 최종적으로는 safe_zone 함수에 tmp를 넣은 결과를 리턴한다.
- 벽 3개를 만드는 함수를 만들어 준다. 파라미터로 벽 개수를 넣어주고 벽 개수가 3개가 되면 bfs함수 결과를 리턴한다.
3개가 안되는 경우엔 현재 위치에 벽을 만들고 이어서 벽을 만드는 과정을 반복해준다.결과적으로 n과 m이 [3,8]이기에 가능했던 문제이다. 만일 n,m 범위가 20,30 까지 늘어났다면 아마 pypy로도 해결이 힘들었을 문제.
벽 3개의 조합을 구성하기 위해 nC3의 반복문을 활용해야 하는데,, 시간을 더 줄일 획기적인 방법이 있는지 고안해볼 필요가 있다.
To be a DataScientist