BFS 문제 중 하나인 연구소 문제이다.
본인이 생각했을 때 문제를 해결하기 위해서는 다음과 같은 조건이 성립되어야 했다.
- 3개의 벽
1을 세울 시 가장 많은 안전 영역을 확보할 수 있어야 한다. - 바이러스는 상하좌우에 위치할 수 있는 빈칸
0을 통해 퍼져나간다. - 벽
1을 넘어가서는 안되며 지도의 크기n * m또한 벗어날 수 없다.
일단 2, 3번의 조건은 무조건 BFS를 적용시킬 수 있는 조건이다.
하지만 1번 조건을 적용시키고자 하니 이것은 분명 기존의 BFS에서 무언가가 더 추가되어야 함을 느꼈다.
그 느낌을 바탕을 생각해보았을 때,
3개의 벽이 세워질 수 있는 모든 경우의 수를 따져 최종적으로 가장 많은
안전구역을 생성하는 결과값을 반환
이것이 정답일 것이라고 생각이 들었다. 따라서 이러한 생각의 구현 과정은 백트래킹을 통해 수행하였다.
전반적인 구성은 다음과 같다
def wall(cnt):
if cnt == 3:
bfs()
return
for i in range(n):
for j in range(m):
if board[i][j] == 0:
board[i][j] = 1
wall(cnt + 1)
board[i][j] = 0해당 코드에서는 벽이 세워질 수 있는 모든 조건에 대해 백트래킹을 통해 찾는다.
cnt 변수는 벽의 개수를 나타내며 초기에는 0의 값이 매개변수로 입력된다.
지도의 크기인 n * m만큼의 반복을 수행하며 해당 위치가 벽을 세울 수 있는 위치인 0일 경우
cnt를 증가시키며 cnt가 3이라는 조건이 성립 될 경우모든 경우의 수에 대해 bfs함수를 수행한다.
def bfs():
queue = deque()
copyBoard = copy.deepcopy(board)
for i in range(n):
for j in range(m):
if copyBoard[i][j] == 2:
queue.append((j, i))
while queue:
px, py = queue.popleft()
for i in range(4):
nx = px + dx[i]
ny = py + dy[i]
if 0<= nx < m and 0 <= ny < n:
if copyBoard[ny][nx] == 0:
copyBoard[ny][nx] = 2
queue.append((nx, ny))
global result
cnt = 0
for i in range(n):
cnt += copyBoard[i].count(0)
result = max(result,cnt)bfs부분이다. 큐를 생성하고 모든 경우의 수에 대해 확인해야하기 때문에 초기에 입력받은 지도 리스트를 가져다
copy하여 사용하였다. 해당 리스트에 대해 반복을 수행하면서 결과를 큐에 집어넣는데, 이는 바이러스에 대하여
갈수있는 모든 지역을 탐색하기 위한 사전작업으로 이해 할 수 있다.
이제 while문을 통해 큐가 비는 순간까지 반복을 수행하며 동, 서, 남, 북 총 네 방향을 통해 나아갈 수 있도록,
나아간 위치에서 감염이 될 수 있는 곳이라면 감염을 수행한 후 해당 위치에서 다시 나아가도록 한다.
결과적으로 바이러스가 나아갈 수 있는 모든 공간이 감염되었을 경우 남아있는 안전구역의 개수를 전역변수로 지정한
result변수와 비교하여 최댓값을 다시 result에 할당할 수 있도록 하였다.
최종 코드는 다음과 같다.
import sys
import copy
from collections import deque
n, m = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
result = 0
def bfs():
queue = deque()
copyBoard = copy.deepcopy(board)
for i in range(n):
for j in range(m):
if copyBoard[i][j] == 2:
queue.append((j, i))
while queue:
px, py = queue.popleft()
for i in range(4):
nx = px + dx[i]
ny = py + dy[i]
if 0<= nx < m and 0 <= ny < n:
if copyBoard[ny][nx] == 0:
copyBoard[ny][nx] = 2
queue.append((nx, ny))
global result
cnt = 0
for i in range(n):
cnt += copyBoard[i].count(0)
result = max(result,cnt)
def wall(cnt):
if cnt == 3:
bfs()
return
for i in range(n):
for j in range(m):
if board[i][j] == 0:
board[i][j] = 1
wall(cnt + 1)
board[i][j] = 0
wall(0)
print(result)
일단 결과는 python3로 수행시 무조건 시간초과가 발생한다. 따라서 pypy3로 작성한 코드를 돌릴것을 권장하는 바 입니다...
