[알고리즘] 백준 14502 연구소 / 파이썬

www.acmicpc.net/problem/14502

14502번: 연구소

 

 

from collections import deque
from copy import deepcopy

dx, dy = [0, -1, 0, 1], [-1, 0, 1, 0]
#bfs이용해 바이러스 퍼뜨림
def virus(i, j, Map2):
    q = deque()
    q.append([i, j])
    while q:
        x, y = q.popleft()
        for k in range(4):
            xx, yy = x + dx[k], y + dy[k]
            if 0 <= xx < N and 0 <= yy < M and Map2[xx][yy] == 0:
                Map2[xx][yy] = 2
                q.append([xx, yy])

def sol(ix, iy, jx, jy, kx, ky):
    Map2 = deepcopy(Map)
    Map2[ix][iy] = 1
    Map2[jx][jy] = 1
    Map2[kx][ky] = 1
    for i in range(N):
        for j in range(M):
            if Map2[i][j] == 2:
                virus(i, j, Map2)
    cnt = sum(i.count(0) for i in Map2)
    return cnt

N, M = map(int, input().split())
Map = [list(map(int, input().split())) for _ in range(N)]
Map2 = deepcopy(Map)
result = 0
#좌표가 아닌 순서로 보고 3개를 고른 다음, 다시 좌표값으로 계산해줌
for i in range(N*M):
    for j in range(i+1, N*M):
        for k in range(j+1, N*M):
            ix, iy, jx, jy, kx, ky = i//M, i%M, j//M, j%M, k//M, k%M
            if Map[ix][iy] == 0 and Map[jx][jy] == 0 and Map[kx][ky] == 0:
                result = max(result, sol(ix, iy, jx, jy, kx, ky))
print(result)