연구소 ( 14502번 )

14502번: 연구소

 

나의 풀이

from itertools import combinations
from collections import deque
import copy
import sys

def _cr_safe(cr_list, n, m):
    answer = 0
    for i in range(n):
        for j in range(m):
            if cr_list[i][j] == 0:
                answer += 1
    return answer

def _sub_main(n, m, map_list, a1, a2, a3, bs_area):
    new_map_list = copy.deepcopy(map_list)
    new_map_list[a1[0]][a1[1]], new_map_list[a2[0]][a2[1]], new_map_list[a3[0]][a3[1]] = 1, 1, 1

    bs_queue = deque(bs_area)
    while bs_queue:
        x, y = bs_queue.popleft()
        for m_x, m_y in ((-1,0),(1,0),(0,1),(0,-1)):
            n_x, n_y = (x + m_x), (y + m_y)
            if (0 <= n_x < n) and (0 <= n_y < m) and (new_map_list[n_x][n_y] == 0):
                new_map_list[n_x][n_y] = 2
                bs_queue.append((n_x, n_y))
    return _cr_safe(new_map_list, n, m)

def _main(n, m, map_list, no_area, bs_area):
    answer = 0
    for a1, a2, a3 in combinations(no_area, 3):
        answer = max(answer, _sub_main(n, m, map_list, a1, a2, a3, bs_area))
    return answer

n, m = map(int, sys.stdin.readline().rstrip().split())
map_list, no_area, bs_area = [], [], []
for idx in range(n):
    append_list = list(map(int, sys.stdin.readline().rstrip().split()))
    map_list.append(append_list)
    for j in range(m):
        if (append_list[j] == 0):
            no_area.append((idx, j))
        if (append_list[j] == 2):
            bs_area.append((idx, j))
print(_main(n, m, map_list, no_area, bs_area))

 

시간 복잡도

for a1, a2, a3 in combinations(no_area, 3) : 빈칸의 조합 생성 (k ** 3)
    answer = max(answer, _sub_main(n, m, map_list, a1, a2, a3, bs_area)) : 내부 계산 함수 ( 이차형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 팔차형 시간 복잡도 ( O(n ** 8) )