[Python] 연구소 - 백준 (BFS)

해당 글은 백준 14502번 문제 '연구소'을 다룬다.

문제

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

14502번: 연구소

 

설명

해당 문제는 3개의 벽을 세울 수 있는 모든 경우의 수에 BFS를 하여 0의 갯수가 최대인 값을 구하면 된다.

3개의 벽을 세울 수 있는 경우는 조합을 통해 구하고, 새로운 배열에 대해서는 deepcopy 함수를 사용하였다.

 

코드

from itertools import combinations
from collections import deque
import copy

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

empty_area = []
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            empty_area.append((i, j))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    q = deque([])
    for i in range(n):
        for j in range(m):
            if new_arr[i][j] == 2:
                q.append((i, j))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx < n and ny >= 0 and ny < m:
                if new_arr[nx][ny] == 0:
                    q.append((nx, ny))
                    new_arr[nx][ny] = 2

result = 0
for combi in combinations(empty_area, 3):
    count = 0
    new_arr = copy.deepcopy(arr)
    for x, y in combi:
        new_arr[x][y] = 1
    bfs()
    for i in range(n):
        for j in range(m):
            if new_arr[i][j] == 0:
                count += 1
    result = max(result, count)
print(result)