[백준] 14502번 : 연구소 (Python3)

입력

첫째 줄에 지도의 세로 크기 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

 

풀이#1

import sys
import copy

input=sys.stdin.readline

N, M=map(int, input().split())
NM=[]
for i in range(N):
    NM.append(list(map(int, input().split())))

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

def select_wall(start, cnt):
    global max_value
    if cnt==3:
        select_NM=copy.deepcopy(NM)
        for x in range(N):
            for y in range(M):
                virus(x, y, select_NM)
        safe_cnt=sum(i.count(0) for i in select_NM)
        max_value=max(max_value, safe_cnt)
        return True
    else:
        for i in range(start, N*M):
            x=i//M
            y=i%M
            if NM[x][y]==0:
                NM[x][y]=1
                select_wall(i, cnt+1)
                NM[x][y]=0

def virus(x, y, select_NM):
    if select_NM[x][y]==2:
        for dir in range(4):
            new_x=x+dx[dir]
            new_y=y+dy[dir]
            if new_x>=0 and new_y>=0 and new_x<N and new_y<M:
                if select_NM[new_x][new_y]==0:
                    select_NM[new_x][new_y]=2
                    virus(new_x, new_y, select_NM)

select_wall(0,0)
print(max_value)