※ 문제링크
해당문제는 DFS와 BFS를 활용하여 풀 수 있는 문제였다. 문제 조건에서 반드시 벽 3개를 설치해야한다고 하였기에 입력값을 배열로 전환하고 벽을 세울 수 있는 조합수를 DFS를 통해 구한 후 조합수별로 배열을 따로 만들어서 조합수만큼 반복문을 돌려 바이러스가 퍼지지 않은 최댓값을 구하려고 하였다. 처음에는 배열을 다 만든다음 한번 더 완전탐색을 해서 바이러스가 퍼지지 않은 지역 개수의 최댓값을 구하려고 했으나, 생각보다 시간과 메모리 조건이 까다로운 것 같아 BFS로 바이러스가 퍼질 수 있는 경우를 탐색할 때마다 바이러스가 퍼진 개수를 세고, 그 수에 벽의 개수를 더한 후 전체 배열의 값의 개수에서 뺀 값으로 바이러스가 퍼지지 않은 개수를 구하는 형태로 코드를 작성하였다. 작성 후 제출하니 python3와 Pypy3에서 모두 통과가 가능하였다.
자세한 풀이방법과 코드는 아래와 같다.
1. 입력받은 값들을 2차원 배열의 형태로 변환한 후 연구소의 위치와 빈 공간은 좌표값을, 벽의 개수를 따로 저장한다.
(연구소의 위치 : BFS로 바이러스가 퍼질 수 있는 공간을 확인시 사용 / 빈 공간 : 벽을 세울 수 있는 조합수 산출시 사용)
2. DFS함수를 활용하여 3개의 벽을 세울 수 있는 모든 경우의 수를 구한다.
(순서가 의미를 가지지 못하므로 수학의 조합과 동일)
3. 각 경우마다 바이러스가 퍼질 수 있는 경우를 구할 수 있는 BFS함수를 작성한다.
4. 바이러스가 퍼지지 않은 공간을 ans로 두고 벽의 조합수만큼 반복문을 돌리면서 모든 경우에 있어 바이러스가 퍼지지 않은 공간의 개수를 산출하고, ans보다 해당 경우의 cnt값이 클 경우 ans를 cnt로 갱신해준다.
5. 반복문이 모두 돌아가면 ans값을 출력한다.
+ 시간 및 메모리 추가단축을 위해 sys함수를 사용하였습니다.
from collections import deque
import sys
N, M = map(int, input().split()) # N : 세로크기(y좌표) / M : 가로크기(x좌표)
field = []
for _ in range(N):
field.append(list(map(int, input().split())))
lab_list = []
space_list = []
wall_num = 0
# 바이러스의 위치, 벽의 위치, 빈 공간의 위치의 좌표를 각각 저장
for y in range(N):
for x in range(M):
if field[y][x] == 0:
space_list.append([x, y])
if field[y][x] == 2:
lab_list.append([x, y])
if field[y][x] == 1:
wall_num += 1
# 벽을 설치할 위치 확인(조합수를 dfs로 확인)
check = [False for _ in range(len(space_list))]
arr = []
com_list = []
def dfs(start):
if len(arr) == 3:
com_list.append(arr[:])
return
for i in range(start, len(check)):
if check[i]:
continue
arr.append(space_list[i])
check[i] = True
dfs(i+1)
arr.pop()
check[i] = False
dfs(0)
# 바이러스가 퍼져나갈 수 있는 상황을 bfs로 작성
dx = [-1, 1, 0, 0]
dy = [0, 0 , -1, 1]
def bfs(lab_list, field):
virus = 0
queue = deque()
for lab in lab_list:
queue.append(lab)
while queue:
virus += 1
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < M and 0 <= ny < N and field[ny][nx] == 0:
field[ny][nx] = 2
queue.append([nx, ny])
return virus
# 벽을 설치한 경우를 배열로 만들어서 저장
ans = 0
field_size = M * N
for i in range(len(com_list)):
cnt = 0
field_sample = []
for t in range(N):
sample = field[t].copy()
field_sample.append(sample)
for k in range(3): # 벽을 반드시 3개를 설치해야함
x, y = com_list[i][k]
field_sample[y][x] = 1
virus = bfs(lab_list, field_sample)
cnt = field_size - (virus + wall_num + 3)
if ans < cnt:
ans = cnt
print(ans)
P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 4963번 섬의 개수 / 사용언어 : 파이썬(python) (0) | 2022.01.15 |
---|---|
[BOJ] 18352번 특정 거리의 도시 찾기 / 사용언어 : 파이썬(python) (0) | 2022.01.14 |
[BOJ] 11724번 연결 요소의 개수 / 사용언어 : 파이썬(python) (0) | 2022.01.13 |
[BOJ] 1707번 이분 그래프 / 사용언어 : 파이썬(python) (0) | 2022.01.12 |
[BOJ] 2206번 벽 부수고 이동하기 / 사용언어 : 파이썬(python) (0) | 2022.01.11 |
댓글