백준_BruteForce_연구소

잘 모르겠다. 예제 코드 잘 돌아가고, 다른 코드랑 비교해도 다른게 없어보이는데 :(

런타임에러가 어디서 나는지 찾아주시면 감사하겠습니다ㅠㅠ

 

import numpy as np
import sys
import copy
ans = 0
n = m = 0
viruslist = []
arr = []
safelist = []

## DFS로 바이러스 퍼트리고, 안전구역 넓이 구하기
def spread_virus(copyed_arr, queue): 
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    visit = list()
    
    while queue:
        node = queue.pop(0) # (1,5)
        if node not in visit:
            visit.append(node)
            copyed_arr[node[0]][node[1]] = 2
            for k in range(4):
                nx = node[0]+dx[k]
                ny = node[1]+dy[k]
                if nx >= 0 and nx < n and ny >= 0 and ny < m:
                    if copyed_arr[nx, ny] == 0:
                        queue.append((nx, ny))
                        
    return n*m - np.count_nonzero(copyed_arr)


def choose_wall(arr, cnt, start):
    global safelist
    
    if cnt == 0 :
        ## 다 고름
        global ans
        copy_arr = copy.deepcopy(arr)
        copy_viruslist = copy.deepcopy(viruslist)
        
        ans = max(ans, spread_virus(copy_arr, copy_viruslist))
        
    else:
        ## 아직 더 골라야함
        for i in range(len(safelist[start:])):
            safe_x, safe_y = safelist[start+i]
            
            arr[safe_x, safe_y] = 1
            choose_wall(arr, cnt-1, start+i+1)
            arr[safe_x, safe_y] = 0
            


if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().strip().split())
    for i in range(n):
        arr.append(list(map(int, sys.stdin.readline().strip().split())))
    arr = np.asarray(arr)
    
    for i in range(n):
        for j in range(m):
            # 바이러스일 경우
            if arr[i][j] == 2: 
                viruslist.append((i,j))
            elif arr[i][j] == 0:
                safelist.append((i,j))
    
    choose_wall(arr, 3, 0)
    print(ans)

 

※ input()보다 sys.stdin.readline()이 더 빠르다고 함

※ 완전 탐색을

   1. 벽 세 개 세울 때는 DFS 사용

   2. 바이러스가 퍼트릴 때는 BFS 사용  → 처음에 생각 못 했던 것

※ array를 복사하는 경우 조심하기 (deepcopy 사용)

   -. 바이러스 리스트 만들어서 바이러스 리스트에 대해서만 퍼트리는 것이 시간단축에 좋음