백준 14502번: 연구소

백준 14052번: 연구소

문제 풀이

• 바이러스가 최소로 퍼지는 벽 3개를 골라 빈 칸(0)의 개수를 구하는 문제
• 0: 빈칸, 1:벽, 2:바이러스
• combinations(조합) 3개 선택, (이 때, 경우의 수를 줄이기 위해서 0에 대한 location 값들을 저장해주어 그 안에서 선택)
• 바이러스 좌표들을 for문을 돌면서 바이러스를 퍼트려줌
• 이 때의 조건
  - 0<=nx<N, 0<=ny<M 절때 까먹지 말 것
  - array[nx][ny] == 0, 퍼트려주고 deque 넣기, 아니면 continue (벽이 없는 경우만 큐에 넣어줌)
• 바이러스를 퍼트려주고 0을 count, 그래서 deepcopy 사용!

개선점

• 시간을 줄이기 위해, len(zero location) -= 1 해줄 수 있을 듯?~?!

Update

• bfs에서의 중요한,, visited 정의 안해줌! 엥 시간초과남,,

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

def spread_virus(board):

    for loc in virus_loc:
        board = spread(board,loc)

    return cnt_empty(board)

def cnt_empty(board):
    cnt = 0
    for i in range(N):
        for j in range(M):
            if board[i][j] == 0:
                cnt += 1

    return cnt

def spread(board,loc):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    new_visit = deque()
    new_visit.append(loc)

    while new_visit:
        curr_loc = new_visit.popleft()
        for i in range(4):
            nx = curr_loc[0] + dx[i]
            ny = curr_loc[1] + dy[i]

            if 0<=nx<N and 0<=ny<M:
                if board[nx][ny] == 0:
                    board[nx][ny] = 2
                    new_visit.append((nx,ny))

    return board



N,M = list(map(int,input().split()))
lab = []
empty_loc = []
virus_loc = []
max_empty = -sys.maxsize

# get iputs and  0 locations
for i in range(N):
    board = list(map(int,input().split()))
    lab.append(board)
    for j,v in enumerate(board):
        if v == 0:
            empty_loc.append((i,j))
        elif v == 2:
            virus_loc.append((i,j))

# all the combinations of empty
for combination in combinations(empty_loc,3):

    copy_arr = deepcopy(lab)
    # spread
    for loc in combination:
        copy_arr[loc[0]][loc[1]] = 1

    after_lab = spread_virus(copy_arr)
    max_empty = max(max_empty, after_lab)

print(max_empty)