파이썬) 연구소

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

14502번: 연구소

 

 

 

즉 주어진 2차원 배열에서 벽(1) 세개를 새워, 0이 가장 많을 때의 개수를 구하는 문제이다

나는 이 문제를 백준-알고리즘 분류 - bfs에서 봤을 땐 어떤 방식으로 풀어야할지 감이 잡히지 않았지만

브루트포스 유형에서 감을 잡게 되었다.

 

풀이법

브루트포스 알고리즘인 만큼 벽을 세울 수 있는 경우의 수를 모두 구하여 0의 개수를 새면 된다.

경우의 수를 구하는 만큼 combinations를 이용했다.

from collections import deque
from itertools import combinations
import copy
n, m = map(int, input().split())


empty = []
virus = []
wall = []

arr = []

for i in range(n):
    a = list(map(int, input().split()))
    arr.append(a)
    for j in range(len(a)):
        if a[j] == 2:
            virus.append([i, j])
        elif a[j] == 1:
            wall.append([i, j])
        else:
            empty.append([i, j])

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

max_cnt = 0

for i in combinations(empty, 3):
    # print(i[0])
    # cnt += 1
    cnt = 0
    graph = copy.deepcopy(arr)
    # graph[i[0][0]][i[0][1]] =
    one = i[0]
    tow = i[1]
    three = i[2]

    # print(one)
    graph[one[0]][one[1]] = 1
    graph[tow[0]][tow[1]] = 1
    graph[three[0]][three[1]] = 1

    q = deque()

    for v in virus:
        q.append((v[0], v[1]))

    while q:
        x, y = q.popleft()

        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 0:
                    q.append((nx, ny))
                    graph[nx][ny] = 2

    for col in graph:
        for row in col:
            if row == 0:
                cnt += 1

    if max_cnt < cnt:
        # print(i)
        max_cnt = cnt


print(max_cnt)