[BFS] 백준 14502번 : 연구소 - 파이썬 Python

 

 

 

 

생각하기

 

처음에는 어떻게 벽 3개를 놓으면 하면 바이러스의(2번의) 확산을 적게할 수 있을까에 대해서 생각했다

 

하지만 고려해야할 변수가 너무 많았다. 

• 벽이 놓였을 때, 어떤 기준으로 해당 자리에 있을 때, 확산이 최소가 되는지
• 벽이 한개도 아니다 세개인데 한개가 맞으면 다른 두개는 어떻게 판단할건지

코드가 복잡해지면 다시 생각하자..

다시 생각하는게 좋았다

 

만약 벽 3개를 N x M 개의 좌표의 각 칸을 대상으로 3개를 뽑는 조합을 구성한다면

 

M이 최대가 8이므로 64 x 63 x 62가 되겠다

 

해당 조합을 기준으로 각각의 바이러스들을 BFS로 하여서 모든 조합 벽배치 조합을 검사하는 방식으로 진행을 하여도

 

64 x 63 x 62 x 64 < 1억 이므로 충분히 시간안에 해결이 가능하다

 

구현하기

• itertools의 combination을 통해 벽 세개의 조합을 만든다
• BFS 방식으로 각각의 벽 조합에 대한 바이러스 확산을 구한다
• 각 확산에서 안전영역의 최대값을 업데이트 한다

import sys
from collections import deque
import copy
import itertools as it

max_safe = 0

input = sys.stdin.readline

N, M = map(int, input().split())

data = []

blank = []

virus = []

wall_cnt = 0
init_virus_cnt = 0

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

for i in range(N):
    data.append(list(map(int, input().split())))
    for j in range(M):
        if data[i][j] == 0:
            blank.append((i, j))
        elif data[i][j] == 2:
            virus.append((i, j))
            init_virus_cnt += 1
        else:
            wall_cnt += 1

comb_wall = list(it.combinations(blank, 3))
# 시간복잡도 : 64 * 63 * 62 *64 = 15,998,976

# print(f'wall_cnt = {wall_cnt}')
# print(f'init_virus_cnt = {init_virus_cnt}')

for comb in comb_wall:
    data_cpy = copy.deepcopy(data)
    for i in range(3):
        data_cpy[comb[i][0]][comb[i][1]] = 1

    virus_cnt = init_virus_cnt

    for v in virus:
        q = deque()
        q.append((v[0], v[1], virus_cnt))
        while len(q) != 0:
            loc = q.popleft()
            for d in range(4):
                ny = loc[0]+dy[d]
                nx = loc[1]+dx[d]
                if 0<=ny<N and 0<=nx<M:
                    if data_cpy[ny][nx]==0:
                        data_cpy[ny][nx] = 2
                        virus_cnt += 1
                        q.append((ny, nx, loc[2]+1))

    max_safe = max(max_safe, N*M-virus_cnt-3-wall_cnt)

print(max_safe)