방화벽 설치하기

아주 예전에 친구들과 1일 1문제 했을 때 풀었던 문제.

위치값 저장해서 방화벽 놓을 수 있는 모든 경우의 수에 불이 퍼지게 해서 최소값만 리턴하면 끝남.

import sys
import copy
from itertools import combinations
from collections import deque

maxCount = 0
copyGraph = []
def bfs(x, y, n , m):
    global copyGraph
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        for z in range(4):
            nx = x + dx[z]
            ny = y + dy[z]
            if 0 <= nx < n and 0 <= ny < m and copyGraph[nx][ny] == 0 :
                copyGraph[nx][ny] = 2
                queue.append((nx, ny))



N, M = map(int,sys.stdin.readline().split())
graph = []
emptyAreaLocation = []
for i in range(N):
    tmpGraphComponent = list(map(int, sys.stdin.readline().split()))
    graph.append(tmpGraphComponent)
for j in range(len(graph)):
    for j2 in range(len(graph[j])):
        if graph[j][j2] == 0 :
            emptyAreaLocation.append([j,j2])
allLocation = list(combinations(emptyAreaLocation,3))
for k in allLocation:
    copyGraph = copy.deepcopy(graph)
    copyGraph[k[0][0]][k[0][1]] = 1
    copyGraph[k[1][0]][k[1][1]] = 1
    copyGraph[k[2][0]][k[2][1]] = 1
    count = 0
    for l in range(len(copyGraph)):
        for l2 in range(len(copyGraph[l])):
            if copyGraph[l][l2] == 2 :
                bfs(l,l2,N,M)
    for j in range(len(copyGraph)):
        for j2 in range(len(copyGraph[j])):
            if copyGraph[j][j2] == 0 :
                count +=1
    maxCount = max(maxCount, count )
print(maxCount)