[Baekjoon]14502. 연구소

1. 초기 아이디어

바이러스가 위치한 구역(arr[i][j] == 2) 주변의 0 개수를 카운트해서 벽 3개로 바이러스를 막을 수 있을 지 여부를 판단하고자 함

바이러스를 모두 동시에 막을 수 없다는 것을 깨달음

2. 변경한 아이디어

벽을 3개만 설치해야하므로 combination을 사용해서 brute-force 함

시간 초과를 방지하기 위해서 계산된 max_area(최대 안전 구역 개수)보다 작아질 경우 bfs를 종료함

 

def bfs():
    global max_area
    delta = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    q = deque()
    q.extend(virus)
    visited = []
    area = 0
    while q:
        x = q[0][0]
        y = q[0][1]
        for d in delta:
            ni = x + d[0]
            nj = y + d[1]
            if 0<=ni<N and 0<=nj<M and arr[ni][nj] == 0 and [ni, nj] not in visited:
                visited.append([ni, nj])
                q.append([ni, nj])
        q.popleft()
        
        # 안전 구역 개수 = area
        area = initial_area-len(visited)
        if max_area > area:
            break

    if max_area < area:
        max_area = area
        return


import sys
from collections import deque
from itertools import combinations
input = sys.stdin.readline

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

wall = []
virus = []
for i in range(N):
    for j in range(M):
        if arr[i][j] == 0:
            wall.append((i, j))
        elif arr[i][j] == 2:
            virus.append([i, j])
            
initial_area = len(wall)-3  # 초기 0 개수
wall_comb = list(combinations(wall, 3))
max_area = 0

for comb in wall_comb:
    # 벽 세우기
    for x, y in comb:
        arr[x][y] = 1
    # bfs 시작
    bfs()
    # 벽 허물기
    for x, y in comb:
        arr[x][y] = 0
print(max_area)

 

메모리 및 시간을 더 효율적으로 쓴 다른 아이디어

- 2차원 행렬을 1차원으로 바꾸어서 시간단축

- deepcopy 활용하여 행렬을 복사함