[ baekjoon ] 14502. 研究所

質問する

人体致命ウイルスを研究する研究所がウイルスを漏らした.幸いにもウイルスはまだ拡散していないので、ウイルスの拡散を防ぐために、研究所に壁を建てたいと思っています.
研究所の大きさはN×Mの矩形として表すことができ、矩形は1である.×1サイズの正方形に分割します.研究所は1つのスペース、1つの壁で構成され、壁は1つのスペースでいっぱいです.
一部の格子にはウイルスが存在し、このウイルスは上下左右に隣接する格子に伝播することができる.新しく立てた壁は3つあるので,3つ立てなければならない.
たとえば、研究所がある場合を見てみましょう.
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
このとき、0はスペース、1は壁、2はウイルスがいる場所です.壁を立てなければ、ウイルスはすべてのスペースに拡散することができます.
2行1列、1行2列、4行6列に壁を設けると、地図の形は以下のようになります.
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
ウイルスが拡散した様子は以下の通りです.
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
3つの壁を設置した後、ウイルスが拡散できない場所を安全区域と呼ぶ.上の地図では、安全区域の大きさは27です.
研究所地図が与えられたタイミングで得られる安全領域の大きさの最値を求めるプログラムを作成した.

入力

第1行は、地図の縦方向サイズNおよび横方向サイズMを与える.(3 ≤ N, M ≤ 8)
2行目からN行目に地図の形状を与える.0はスペース、1は壁、2はウイルスの位置です.2の個数は2以上、10以下の自然数である.
スペースの数は3つ以上です.

しゅつりょく

最初の行で取得できるセキュリティ領域の最大サイズを出力します.

3つの壁を取り付けたときの合計数を計算する必要があります
1.3つの壁を立てる
2.ウイルス伝播
3.安全区域の最大更新

# 14502. 연구소
import sys
import copy

input = sys.stdin.readline
n, m = map(int, input().split())
result = 0
maps = []

# 벽 설치한 뒤 리스트
temp = [[0 for j in range(m)] for i in range(n)]

for _ in range(n):
  tmp = list(map(int, input().split()))
  maps.append(tmp)

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

def virus(x, y): # x, y 좌표의 상하좌우 바이러스 퍼뜨리기
  for i in range(4):
    nx = dx[i] + x
    ny = dy[i] + y
    if nx >= 0 and nx < n and ny >= 0 and ny < m: # 지도 밖인지 범위 체크
      if temp[nx][ny] == 0:
        temp[nx][ny] = 2 # 바이러스 전염
        virus(nx, ny) # 재귀 함수 호출

# 안전 영역 크기 구하기
def max_area(): 
  area = 0
  for i in range(n):
    # for j in range(m):
    #   if temp[i][j] == 0:
    #     area += 1
    area += temp[i].count(0)
  return area
  
# dfs를 이용해 벽을 설치하면서, 매번 안전영역 크기 계산
def dfs(count):
  global result # 리턴값
  global temp

  if count == 3: # 벽 3개 모두 설치한 경우
    temp = copy.deepcopy(maps) # global 선언 해줘야 함
    # for i in range(n):
    #   for j in range(m):
    #     temp[i][j] = maps[i][j]
    
    for i in range(n):
      for j in range(m):
        if temp[i][j] == 2:
          virus(i, j)
    result = max(result, max_area()) # 안전영역 최대 크기 갱신

    return

  # count가 3이 아닌 경우(벽 설치할 수 있는 경우)
  # 빈 공간에 벽 설치
  for i in range(n): # 모든 경우의 수
    for j in range(m):
      if maps[i][j] == 0:
        maps[i][j] = 1 # 벽 설치
        count += 1
        dfs(count)
        maps[i][j] = 0 # 되돌리기
        count -= 1 
  
dfs(0)
print(result)

すべての场合、税収问题は最も解决しにくいようですが、迷いはいつも答えを见ています.
こちらです.
copyライブラリを知って、deepcopyをするときはglobalを宣言してこそ正しい答えが得られます.
この2つのコードのように

 global temp
 temp = copy.deepcopy(maps) # global 선언 해줘야 함

for i in range(n):
	for j in range(m):
		temp[i][j] = maps[i][j]

また、リストで所定の値を検索する場合はcount関数を使用できます!
この2つのコードは同じです

 area = 0
 for i in range(n):
    area += temp[i].count(0)

for j in range(m):
	if temp[i][j] == 0:
		area += 1

DFSもBFSも可能!
すべてのコードがまとめられていて、理解しにくいです.
これは54点の正解率で、最近見た問題の中で最も難しいことです.
いずれにしても、よく復習しなければなりません.