[백준 14502] 연구소

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

14502번: 연구소

[문제] 생략

---

[입력]

 

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈칸의 개수는 3개 이상이다.

---

[출력]

 

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

 

1. matrix를 입력받는 과정에서 zero point와 two point의 좌표를 저장합니다. zero_point 리스트는 임의의 벽 3개를 세울 수 있는 후보지역으로 사용됩니다. 

 

2. vir 함수는 일반적인 bfs 함수이지만, 임의의 벽 3개를 세울 수 있는 경우의 수마다 호출해야 하기 때문에 원본 matrix를 입력받아 copy 하여 사용합니다. 

 

3. 임의의 벽 3개를 세울 수 있는 모든 경우의 수에서 바이러스가 가장 적게 퍼진 즉, matrix 내에서 0이 가장 많은 경우의 0의 개수를 출력합니다.

 

import sys
from copy import deepcopy
from itertools import combinations
X,Y = map(int, sys.stdin.readline().split(" "))

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

matrix = []

zero_point = []
two_point = []
for i in range(X):
    matrix.append(list(map(int, sys.stdin.readline().split(" "))))
    for j in range(Y):
        if matrix[i][j]==0:
            zero_point.append([j,i])
        elif matrix[i][j]==2:
            two_point.append([j,i])
        
answer = 0

def vir(start, tmp_wall , matrix):
    global two_point
    m,n = start
    matrix = deepcopy(matrix)
    for i in tmp_wall:
        matrix[i[1]][i[0]]=1
    for i in two_point:
        queue = [i]
        while queue:
            m,n = queue.pop()
            for k in range(4):
                ax = m+dx[k]
                ay = n+dy[k]
                if ax>=0 and ax<Y and ay>=0 and ay<X:
                    if matrix[ay][ax]==0:
                        queue.append([ax,ay])
                        matrix[ay][ax]=2

    return sum(matrix, []).count(0)

candi = list(combinations(zero_point,3))

for kk in candi:
    answer = max(answer, vir([i,j], kk, matrix))
            
print(answer)