[python] 백준 14502 연구소

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

14502번: 연구소

 

문제 해결

• 벽을 어떻게 세워야하는가? → 상황에 따라 다르다. So 모든 경우 다 해봐야 한다. 재귀 사용!
• 최대 영역을 어떻게 구하는가? 전염 되는 지역을 계속 이동 시킨 후 더이상 전염이 안될 때 전염이 안된 일반 지역의 구역 개수를 구하면 된다.
• 전염지역 구하기 위해 bfs() 할 때 계속 graph 값이 바뀌므로 copy.deepcopy를 이용해 복사본으로 돌리는 것이 좋다! copy 라이브러리 알아두자! (리스트는 Mutable 하기 때문에 deepcopy를 이용해야한다!)

CODE

import sys
input = sys.stdin.readline
from collections import deque
import copy
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
move = [(-1,0), (1,0), (0,-1), (0,1)]
ans = 0
def make_wall(cnt):
    global ans
    if cnt == 3:
        bfs()
        return
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                make_wall(cnt+1)
                graph[i][j] = 0

def bfs():
    global ans
    que = deque()
    graph_1 = copy.deepcopy(graph)
    for i in range(n):
        for j in range(m):
            if graph_1[i][j] == 2:
                que.append((i,j))
    while que:
        x, y = que.popleft()
        for next in move:
            nx = x + next[0]
            ny = y + next[1]
            if nx<0 or nx>=n or ny<0 or ny>=m: continue
            elif graph_1[nx][ny] == 0:
                graph_1[nx][ny] = 2
                que.append((nx,ny))
    safe = 0
    for i in range(n):
        for j in range(m):
            if graph_1[i][j] ==0:
                safe += 1
    ans = max(ans,safe)

make_wall(0)
print(ans)