[Algorithm] BaekJoon : 14502. 研究所by Python

[質問へ]https://www.acmicpc.net/problem/14502

📌問題の説明

人体致命ウイルスを研究する研究所がウイルスを漏らした.幸いにもウイルスはまだ拡散していないので、ウイルスの拡散を防ぐために、研究所に壁を建てたいと思っています.
研究所の大きさはN×Mの矩形として表すことができ、矩形は1である.×1サイズの正方形に分割します.研究所は1つのスペース、1つの壁で構成され、壁は1つのスペースでいっぱいです.
一部の格子にはウイルスが存在し、このウイルスは上下左右に隣接する格子に伝播することができる.新しく立てた壁は3つあるので,3つ立てなければならない.
たとえば、研究所がある場合を見てみましょう.

このとき、0はスペース、1は壁、2はウイルスがいる場所です.壁を立てなければ、ウイルスはすべてのスペースに拡散することができます.
2行1列、1行2列、4行6列に壁を設けると、地図の形は以下のようになります.

ウイルスが拡散した様子は以下の通りです.

3つの壁を設置した後、ウイルスが拡散できない場所を安全区域と呼ぶ.上の地図では、安全区域の大きさは27です.
研究所地図が与えられたタイミングで得られる安全領域の大きさの最値を求めるプログラムを作成した.
入力
第1行は、地図の縦方向サイズNおよび横方向サイズMを与える.(3 ≤ N, M ≤ 8)
2行目からN行目に地図の形状を与える.0はスペース、1は壁、2はウイルスの位置です.2の個数は2以上、10以下の自然数である.
スペースの数は3つ以上です.
しゅつりょく
最初の行で取得できるセキュリティ領域の最大サイズを出力します.

💡 問題を解く

DFS/BFS+の組み合わせで問題が解決した.
2 D配列の大きさは最大8 x 8であり、すべての要素が0であっても、最悪の場合は64 C 3(=41664)であり、組み合わせの使用に適している回数である.
step 1)
変数の宣言

壁:壁(要素0)座標となるアレイを全て含む

ウイルス:全てのウイルス(元素が2)座標を含む配列

matrix:与えられた二次元アレイ(NxM)

答:安全区域の大きさを含む変数(最大値を探す)

step 2)
3つの壁を立てなければならないので、壁の候補者の中から3つの座標を選択します.→組み合わせを使う
step 3)
選択した3つの座標で壁を立てた後、DFSを利用してウイルスを最大限に伝播します.
step 4)
ウイルス転送が完了すると、検索するセキュリティ領域(要素は0)のサイズが計算されます.→計算関数

cnt:セキュリティ領域数

その後、答え値をcnt値と比較し、最大値で答え値を更新します.
コードは次のとおりです.

import sys
from itertools import combinations
from copy import deepcopy

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def calculate(matrix):
    global N, M, answer
    cnt = 0
    for r in range(N):
        for c in range(M):
            if matrix[r][c] == 0:
                cnt += 1
    answer = max(answer, cnt)

def dfs(matrix):
    stack = deepcopy(viruses)
    while stack:
        vi = stack.pop()
        for idx in range(4):
            nr = vi[0] + d[idx][0]
            nc = vi[1] + d[idx][1]
            if 0 <= nr < N and 0 <= nc < M:
                if matrix[nr][nc] == 0:
                    matrix[nr][nc] = 2
                    stack.append((nr, nc))
    calculate(matrix)

def test(wall, matrix):
    for w in wall:
        matrix[w[0]][w[1]] = 1
    dfs(matrix)


N, M = map(int, sys.stdin.readline().split())

walls = []
viruses = []
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
answer = 0

for r in range(N):
    for c in range(M):
        if matrix[r][c] == 0:
            walls.append((r, c))
        elif matrix[r][c] == 2:
            viruses.append((r, c))

for wall in combinations(walls, 3):
    test(wall, deepcopy(matrix))
print(answer)

コンビネーションを使用すると簡単に解けますが、再帰を使用してDFS(?)に似ています.次のようにコードで表します.(Python 3-「タイムアウト」/PyPy 3-通過)

import sys

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
N, M = map(int, sys.stdin.readline().split())
matrix = []
temp = [[0] * M for _ in range(N)]

for _ in range(N):
    matrix.append(list(map(int, sys.stdin.readline().split())))

answer = 0

def calculate():
    cnt = 0
    for r in range(N):
        for c in range(M):
            if temp[r][c] == 0:
                cnt += 1
    return cnt

def virus(r, c):
    for idx in range(4):
        nr = r + d[idx][0]
        nc = c + d[idx][1]
        if 0 <= nr < N and 0 <= nc < M:
            if not temp[nr][nc]:
                temp[nr][nc] = 2
                virus(nr, nc)

def dfs(count):
    global answer
    if count == 3:
        for r in range(N):
            for c in range(M):
                temp[r][c] = matrix[r][c]
        for r in range(N):
            for c in range(M):
                if temp[r][c] == 2:
                    virus(r, c)
        answer = max(answer, calculate())
        return

    for r in range(N):
        for c in range(M):
            if not matrix[r][c]:
                matrix[r][c] = 1
                count += 1
                dfs(count)
                matrix[r][c] = 0
                count -= 1
dfs(0)
print(answer)

私はBFSをよく使いますが、DFSにも詳しいです(特に再帰的に実現しています...)😃