[백준] 14502번-(Python 파이썬) - Bfs, Dfs, Brute Force

문제링크 : https://www.acmicpc.net/problem/14502

이번 문제는 정답 비율을 보고 만만하게 봤다가 크게 혼난 문제이다.
바이러스를 탐색하는건 bfs를 이용하여 간단하게 해결하였지만, 벽을 세우는 부분에서 막혀 한참을 고민하다가
결국 다른분의 코드를 보고 다시 풀었다. 브루트 포스로 다 때려박는 풀이는 상상도 못한... ㅠ
아직 많이 부족한걸 느낀 문제이다.

import sys, copy
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
max_num = 0

empty_list = []
virus_list = []

EMPTY = 0
WALL = 1
VIRUS = 2

graph = []

for y in range(n):
    graph.append(list(map(int, input().split())))
    for x in range(m):
        if graph[y][x] == EMPTY:
            empty_list.append([y, x])
        if graph[y][x] == VIRUS:
            virus_list.append([y, x])
    
def bfs(g):
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]

    global max_num

    q = deque()
    visit = [[0] * m for _ in range(n)]
    cnt = 0

    for v in virus_list:
        q.append(v)
    
    while q:
        y, x = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < m and 0 <= ny < n \
                and visit[ny][nx] == 0 and g[ny][nx] == EMPTY:
                g[ny][nx] = VIRUS
                visit[ny][nx] = 1
                q.append([ny, nx])

    for i in range(n):
            cnt += g[i].count(EMPTY)
        
    if max_num < cnt:
            max_num = cnt

for i in range(len(empty_list)):
    for j in range(i):
        for k in range(j):
            y1, x1 = empty_list[i]
            y2, x2 = empty_list[j]
            y3, x3 = empty_list[k]

            graph[y1][x1] = WALL
            graph[y2][x2] = WALL
            graph[y3][x3] = WALL

            g = copy.deepcopy(graph)
            bfs(g)

            graph[y1][x1] = EMPTY
            graph[y2][x2] = EMPTY
            graph[y3][x3] = EMPTY

print(max_num)