[BOJ][Python]14502 풀이

https://www.acmicpc.net/problem/14502

14502번: 연구소

from collections import deque
import copy
import sys
ssr = sys.stdin.readline

def bfs(n, m, board, twos):
    dpos = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = deque(twos)
    while q:
        v_r, v_c = q.popleft()
        for dr, dc in dpos:
            pos_r, pos_c = v_r+dr, v_c+dc
            if 0 <= pos_r < n and 0 <= pos_c < m:
                if board[pos_r][pos_c] == 0:
                    board[pos_r][pos_c] = 2
                    q.append((pos_r, pos_c))
    zero_cnt = 0
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                zero_cnt += 1
    return zero_cnt
                
def func(n, m, board, zeros, twos):
    result = 0
    for i in range(len(zeros)-2):
        board[zeros[i][0]][zeros[i][1]] = 1
        for j in range(i+1, len(zeros)-1):
            board[zeros[j][0]][zeros[j][1]] = 1
            for k in range(j+1, len(zeros)):
                board[zeros[k][0]][zeros[k][1]] = 1
                tmp = bfs(n, m, copy.deepcopy(board), twos)
                if tmp > result:
                    result = tmp
                board[zeros[k][0]][zeros[k][1]] = 0
            board[zeros[j][0]][zeros[j][1]] = 0
        board[zeros[i][0]][zeros[i][1]] = 0
    return result

n, m = map(int, ssr().split())
board = [list(map(int, ssr().split())) for _ in range(n)]
viruses = []
spaces= []
for i in range(n):
    for j in range(m):
        if board[i][j] == 2:
            viruses.append((i, j))
        elif board[i][j] == 0:
            spaces.append((i, j))
ans = func(n, m, board, spaces, viruses)
print(ans)

구현이 어려운 문제는 아닌데 런타임을 줄이는 건 조금 생각을 해봐야 할 문제인 것 같습니다. 0의 갯수를 직접 세지 않고 갯수를 미리 저장해뒀다가 0이 2로 바뀌면 갯수를 하나씩 줄이는 방법으로 코드를 고쳐봤었는데 그래도 400ms가 한계더라구요. 이백대의 런타임이 나오려면 뭔가 새로운 방법을 생각해봐야 할 것 같습니다.

 

런타임에 신경을 쓰지 않으신다면 입력이 작아서 엄청 비효율적이라고 생각되는 풀이도 그냥 통과하니까 풀고 넘어가셔도 될 것 같네요.