[BOJ] 14502 연구소

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

문제요약

• 2차원 배열이 주어진다.
• 0 : 바닥, 1 : 벽, 2 : 바이러스를 의미한다.
• 바이러스는 인접한 땅에 증식할 수 있다.
• 임의로 벽을 3개 세울 수 있을 때, 바이러스가 증식하지 못하는 안전영역의 최대 수를 출력하라.

접근

• 모든 바닥에 3개의 벽을 세울 수 있는 경우의 수를 구한다.
• 위에서 구한 여러 케이스에 대한 좌표값을 1(벽)로 변경한다.
• 바이러스와 인접한 땅에 대해 상,하,좌,우로 이동하면서 바이러스를 의미하는 2로 변경한다.
• 2차원 배열을 돌면서 바이러스가 증식하지 못한 안전영역의 개수를 구한다.
• 안전영역의 개수가 이전에 구했던 값 보다 큰 경우 갱신한다.

코드

import sys
import itertools
import copy

def dfs(y,x):
    for i in range(4):
    	# 상하좌우 탐색
        ny=y+dy[i] 
        nx=x+dx[i]
        if 0 <= ny < n and 0 <= nx < m:
            if laboratory_test[ny][nx]==0:
                if not visited[ny][nx]:
                    visited[ny][nx]=True
                    laboratory_test[ny][nx]=2
                    dfs(ny,nx) 

n,m=map(int,input().split())
laboratory=[list(map(int,sys.stdin.readline().split())) for i in range(n)]
location=[]
dy=(-1,1,0,0)
dx=(0,0,-1,1)
max_safety_area=0

for i in range(len(laboratory)):
    for j in range(len(laboratory[i])):
        if laboratory[i][j]==0:
            location.append((i,j))
candidate=list(itertools.combinations(location,3)) # 벽을 세우는 여러 케이스

for i in candidate:
    laboratory_test=copy.deepcopy(laboratory)
    visited=[[False]*m for _ in range(n)]
    safety_area=0
    
    for j in i: # 세 개의 벽을 만든다
        laboratory_test[j[0]][j[1]]=1
 
    for y in range(len(laboratory_test)):
        for x in range(len(laboratory_test[y])):
            if laboratory_test[y][x]==2: # 바이러스이면 
                if not visited[y][x]:
                    visited[y][x]=True
                    dfs(y,x)

    for y in range(len(laboratory_test)):
        for x in range(len(laboratory_test[y])):
            if laboratory_test[y][x]==0: # 안전영역의 수 카운트
                safety_area+=1
    max_safety_area=max(max_safety_area,safety_area)

print(max_safety_area)