14502_연구소

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

14502번: 연구소

 

 

 

벽을 세운 후에 미로를 풀면 된다.

 

바이러스를 퍼뜨리는것을 함수로 만들어서 dfs로 구현하였다.

 

그후 바이러스가 있다면 주위로 퍼져나가게끔 2차원 배열 전체에서 dfs를 한번씩 실행한 후에, 나온 보드에서 0의 개수를 세주며 업데이트를 해준다.

 

벽을 3개 세워줘야 하는데, 중요한건 꼭 3개가 채워져야 한다는 것 즉, 전체 배열 중에서 3개를 순열로 뽑아내서 m으로 나눈후 몫을 x좌표, 나머지를 y좌표로 삼아 3개가 채울수 있는경우에만 전체적으로 dfs를 설정해주었다.

 

나는 board 를 전역변수로 설정해두었기에, 초기상태 지도를 저장할 old_board를 만들어둬서 dfs를 돌릴때마다 갱신하도록 해 주었다.

 

import sys
from itertools import combinations
input = sys.stdin.readline

n,m = map(int,input().split())
board = [ list(map(int,input().split())) for _ in range(n) ]

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


def dfs(x,y):
    if board[x][y] !=2:
        return

    for i in range(4):
        nx,ny = x + dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m and not board[nx][ny]:
            board[nx][ny] = 2
            dfs(nx,ny)

def check_dfs():
    for i in range(n):
        for j in range(m):
            dfs(i,j)

    cnt = 0
    for i in board:
        for j in i:
            if j == 0:
                cnt +=1
    return cnt

old_board = [ x[:] for x in  board ]
result = 0
for combi in combinations(range(n*m),3):

    tmp = []
    for i in combi:
        tmp.append([i//m,i%m])


    board = [ x[:] for x in old_board]

    for x,y in tmp:
        if board[x][y] != 0:
            break
        board[x][y] = 1
    else:
        result = max(result,check_dfs())

print(result)