[BOJ] 14502번 연구소 / 사용언어 : 파이썬(python)

※ 문제링크

14502번: 연구소

해당문제는 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 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.