연구소

💻 입력 조건

• 첫째 줄에 지도의 세로크기 N과 가로 크기 M이 주어집니다. (3 <= N, M <= 8)
• 둘째 줄부터 n 개의 줄에 지도의 모양이 주어집니다. 0은 빈칸, 1 은 벽, 2는 바이러스가 있는 위치입니다.
• 2의 개수는 2보다 크거나 같고, 10보다 크거나 같은 자연수입니다.
• 빈칸의 개수는 3개 이상입니다.

💻 출력 조건

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

💻 입력 예시1

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0 
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0 

💻 출력 예시1

27

💻 입력 예시2

4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2 
0 0 0 0 0 2 

💻 출력 예시2

9

💻 입력 예시3

8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2 
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 

💻 출력 예시3

3

📖 문제 해결
itertools 내의 combination 모듈을 이용하여 가능한 1의 좌표들의 조합을 모두 구한 후, 각 경우들에 대하여 바이러스를 최대한 퍼뜨린 후 남아있는 0의 개수를 세는 방식으로 코드를 작성하였습니다. 이때 '바이러스를 최대한 퍼뜨리는 함수'를 bfs 알고리즘을 이용하여 작성하였습니다.

# n과 m의 값 입력 받기
n, m = list(map(int,input().split()))

# 지도의 모양 입력 받기
input_map = []
for i in range(n):
    input_map.append(list(map(int,input().split())))

# 0의 좌표들을 입력 받기
coordinates = []
for r_idx, row in enumerate(input_map):
    for c_idx, col in enumerate(input_map):
        if input_map[r_idx][c_idx] == 0:
            coordinates.append((r_idx,c_idx))

# 가능한 1의 좌표들의 조합 계산하기
from itertools import combinations
comb_coordinates = list(combinations(coordinates, 3))

from collections import deque

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

# 바이러스 전염 함수 만들기
def virus(input_map):
    
    queue = deque()
    count = 0
    
    for r_idx, row in enumerate(input_map):
        for c_idx, col in enumerate(input_map):
            if input_map[r_idx][c_idx] == 2:
                queue.append((r_idx,c_idx))
    
    while queue:
        virus_coordinate = queue.popleft()
        for i in range(4):
            minimum_ = 0 <= virus_coordinate[0]+dx[i] and 0 <= virus_coordinate[1]+dy[i]
            maximum_ = virus_coordinate[0]+dx[i] < n and virus_coordinate[1]+dy[i] < m
            if minimum_ and maximum_ and input_map[virus_coordinate[0]+dx[i]][virus_coordinate[1]+dy[i]] == 0 :
                input_map[virus_coordinate[0]+dx[i]][virus_coordinate[1]+dy[i]] = 2
                queue.append((virus_coordinate[0]+dx[i],virus_coordinate[1]+dy[i]))
                
    for r_idx, row in enumerate(input_map):
        for c_idx, col in enumerate(input_map):
            if input_map[r_idx][c_idx] == 0:
                count += 1
    
    return count

import copy

safety_zone = []

for comb_coordinate in comb_coordinates:
    
    input_map_copy = copy.deepcopy(input_map)

    # 조합의 한 가지 경우의 수에 대하여 계산해보기 시작
    for coordinate in comb_coordinate:
        # print(coordinate)
        input_map_copy[coordinate[0]][coordinate[1]] = 1
        
     # 이 경우에 대하여 바이러스가 퍼진 이후 계산 및 0 개수 세기
    safety_zone.append(virus(input_map_copy))

print(max(safety_zone))