[Python][백준] 14502번 연구소

https://www.acmicpc.net/problem/14502

공부 날짜 : 2022.08.27
정답 참조 여부 : X

실험실에 바이러스가 퍼졌을때 3개의 벽으로 바이러스의 확산을 최소화 시켰을때 빈칸의 개수를 구하는 문제이다.

바이러스가 확산되는 방식은
1. 바이러스의 위치를 저장
2. 저장된 바이러스를 pop로 리스트에서 제거하고 바이러스를 확산
3. 확산된 바이러스의 위치를 저장
의 방식을 반복했고 리스트에 저장된 바이러스가 없을때 빈칸의 개수를 세는식으로 코드를 작성했다.

하지만 벽을 어디세울지가 문제였는데 처음 생각은 바이러스를 확산시키면서 확산 가능한 방향이 하나일때 벽을세우려고 했으나 바이러스가 2개이상일때 순서에 따라 달라질수 있는 문제가 있었다.

벽을 세우는 방법은 실험실로 주어지는 n과 m의 크기가 최대 8로 많아야 64개 밖에 없다는 점에서 빈칸중에 3개를 골라 하나씩 벽을 세워보고 그 상황에 따라 확산 시뮬레이션 했을때 빈칸의 개수를 세서 최대값을 갱신시켜줬더니 정답으로 나왔다.

소스코드

import sys
from copy import deepcopy as copy
input = sys.stdin.readline

n,m = map(int, input().split())

graph = []
virus = []
non_area = []

#데이터 입력받으면서 바이러스와 빈칸의 좌표를 저장
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(m):
        if a[j] == 2:
            virus.append([i,j])
        elif a[j] == 0:
            non_area.append([i,j])
    graph.append(a[:])

#상하좌우
dx = [0,1,0,-1]
dy = [1,0,-1,0]

result = 0

#확산 함수
def diffusion(graph):
    global result
    
    while virus_copy:
        x,y = virus_copy.pop(0)
        
        for dir in range(4):
            nx = x+dx[dir]
            ny = y+dy[dir]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
                
            if graph[nx][ny] == 0:
                graph[nx][ny] = 2
                virus_copy.append([nx,ny])
                
            else:
                continue
                
    result = max(result, count_non_area(graph))

#빈칸의 개수를 세는 함수
def count_non_area(graph):
    count = 0
    
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                count += 1
    
    return count
                


for i in range(len(non_area)):
    for j in range(i+1, len(non_area)):
        for k in range(j+1, len(non_area)):
            check_graph = copy(graph)
            virus_copy = copy(virus)
            check_graph[non_area[i][0]][non_area[i][1]] = 1
            check_graph[non_area[j][0]][non_area[j][1]] = 1
            check_graph[non_area[k][0]][non_area[k][1]] = 1
            
            diffusion(check_graph)


print(result)