백준 14502 연구소(with Python)

• 다른 사람의 아이디어와 별차이가 없는데 시간이 5배 넘게 차이난다...

• collections로 테스트 해봤는데, 그 문제는 아닌거 같고... deepcopy로 매번 통째로 다시 선언하는게 나으려나?

  • 최적화는 어려워... ㅠ

from collections import deque

# N: 세로
# M: 가로
N, M = map(int, input().split())

brd = [list(map(int, input().split())) for _ in range(N)]

initial_viruse_locations = []
empty_locations = []
num_walls = 0
for r in range(N):
    for c in range(M):
        if brd[r][c] == 2:
            initial_viruse_locations.append([r, c])
        if brd[r][c] == 1:
            num_walls += 1
        if brd[r][c] == 0:
            empty_locations.append([r, c])

# 어차피 벽은 무조건 3개 더 설치할거니까 += 3
num_walls += 3

nums_initial_viruses = len(initial_viruse_locations)
min_num_viruses = N*M

# 주어진 brd에서 빈 곳 3군데를 뽑아서 칸을 설치하고
# 바이러스 퍼지는 정도를 확인해보자. (완전탐색)
len_empties = len(empty_locations)
# e1_idx: 비어있는 공간 중 한 곳의 인덱스
for e1_idx in range(len_empties-2):
    for e2_idx in range(e1_idx+1, len_empties-1):
        for e3_idx in range(e2_idx, len_empties):
            e1_r, e1_c = empty_locations[e1_idx]
            e2_r, e2_c = empty_locations[e2_idx]
            e3_r, e3_c = empty_locations[e3_idx]

            # 벽설치
            brd[e1_r][e1_c] = 1
            brd[e2_r][e2_c] = 1
            brd[e3_r][e3_c] = 1

            # 바이러스 퍼지는 정도 확인하기
            tmp_num_viruses = nums_initial_viruses
            queue = initial_viruse_locations[:]
            queue = deque(queue)
            new_virus_locations = []
            is_terminate = False
            while queue and not is_terminate:
                vr, vc = queue.popleft()
                for dr, dc in [[1, 0], [0, 1], [0, -1], [-1, 0]]:
                    if 0 <= vr+dr < N and 0 <= vc+dc < M and brd[vr+dr][vc+dc] == 0:
                        queue.append([vr+dr, vc+dc])
                        brd[vr+dr][vc+dc] = 2
                        new_virus_locations.append([vr+dr, vc+dc])
                        tmp_num_viruses += 1
                        if min_num_viruses < tmp_num_viruses:
                            # 이 경우에는 기존보다 안전영역이 적을 수 밖에 없으므로 탐색 무의미
                            is_terminate = True
                            break
            if min_num_viruses > tmp_num_viruses:
                min_num_viruses = tmp_num_viruses

            # 벽제거, 바이러스 제거
            brd[e1_r][e1_c] = 0
            brd[e2_r][e2_c] = 0
            brd[e3_r][e3_c] = 0
            for vr, vc in new_virus_locations:
                brd[vr][vc] = 0

print(N*M - num_walls - min_num_viruses)