[백준] 14502 - 연구소(파이썬, Python)

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

 

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

14502번: 연구소

 

이 문제는 3개의 벽을 세우고 바이러스가 확산된 후 남아 있는 안전 영역을 계산하는 문제입니다.

 

저는 이 문제를 풀 때 새로운 벽의 위치를 선정하는 방법에 대한 많은 고민을 했습니다.

결론적으로 기발한 방법은 생각하지 못했고 Combination을 이용했습니다.

 

해당 문제에 대한 저의 접근법은 아래와 같습니다.

 

접근법

1. 연구소의 빈 곳 중 조합을 이용해서 벽이 세워질 후보 장소 3곳을 선정하고 벽을 세웁니다.

2. 벽이 세워진 상태에서 바이러스가 확산시킵니다.(dfs를 이용했습니다.)

2.1 바이러스가 확산할 때 새로 확산된 공간의 수를 계산합니다.

3. (초기 안전 영역의 크기) - (바이러스가 새로 확산된 공간의 크기)가 가장 커지는 값을 출력합니다.

 

전체 코드는 아래와 같습니다.

 

전체 코드

import sys
from itertools import combinations
from copy import deepcopy

N, M = map(int, sys.stdin.readline().strip().split())

mat = [[0]*M for _ in range(N)]

zeroPos = []
twoPos = []
maxSafeZone = 0

for i in range(N):
    row = list(map(int, sys.stdin.readline().strip().split()))
    
    for j in range(M):
        mat[i][j] = row[j]

        if row[j] == 0:
            maxSafeZone += 1
            zeroPos.append((i, j))
        elif row[j] == 2:
            twoPos.append((i, j))

maxSafeZone -= 3
answer = 0

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

for positions in combinations(zeroPos, 3): #combination으로 벽이 세워질 장소 정하기
    cnt_trans = 0
    temp_mat = deepcopy(mat)

    for pos in positions:
        row, col = pos
        temp_mat[row][col] = 1
        
    stack = deepcopy(twoPos)

    while stack:
    # 바이러스 확산 시키기
        curR, curC = stack.pop()

        for i in range(4):
            if 0 <= curR+dy[i] < N and 0 <= curC+dx[i] < M and temp_mat[curR+dy[i]][curC+dx[i]] == 0:
                temp_mat[curR+dy[i]][curC+dx[i]] = 2
                cnt_trans += 1
                stack.append((curR+dy[i], curC+dx[i]))

    
    # 남아 있는 안전 영역의 최대 값 구하기
    if answer < maxSafeZone - cnt_trans:
        answer = maxSafeZone - cnt_trans

print(answer)