白駿14502:研究所

2日前からdfsとbfsに本格的に接触し、bfsだけでなくbruteforceも一緒に考えている問題があるので、伝言を残したいと思います.
(+一人で10分悩んで、初めて一人で金の問題を解決したので、直接明らかにすることはできません)
まず,問題の詳細を見ると,3つの研究所の壁を構築することによってウイルス感染を最小化するアルゴリズムに迷いを覚えるとともに,brutforceで十分に解決できるという条件を調べた.
第1行は、地図の縦方向サイズNおよび横方向サイズMを与える.(3 ≤ N, M ≤ 8)
タイムアウト:2秒
メモリ制限:512 MB
まず、図中の0部について、組合せとして3つを選択して図に追加する.この場合,各ケースの数を考慮してグラフィックを再コピーし,そのグラフィック上で探索する必要があるためdeepcopyを用いた.
compositionとdeepcopyのコードは以下の通りです.

import sys, copy
from itertools import combinations

# combination
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            wall_list.append( (i, j) )
        if graph[i][j] == 0:
            wall_candidate.append( (i, j) )

wall_comb = list(combinations(wall_candidate, 3))



#deepcopy
graph_ = copy.deepcopy(graph)

次に、ノード全体をbfs(ウイルスが落ちる可能性がある)ずつ回転させ、アクセスしたり、壁、ダブルノードを通過したりします.1回のloopが終了した後、グラフに0の値を計算して保存し、保存したcount値の中で最大の値を見つけた場合、ウイルス伝播が最小化されたときに感染していないノードの数を3つの壁だけで求めることができる.
ソースコード全体を以下に示します.

import sys, copy
from itertools import combinations
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = [ list(map(int, sys.stdin.readline().split())) for i in range(n)]

wall_list = []
#0인 노드들의 후보 리스트
wall_candidate = []

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            wall_list.append( (i, j) )
        if graph[i][j] == 0:
            wall_candidate.append( (i, j) )

#0인 노드들의 후보리스트에서 3개를 선택한 조합들의 리스트, 리스트의 길이는 len(wall_candidate) C 3
wall_comb = list(combinations(wall_candidate, 3))
#이동할 방향을 정의(상하좌우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(graph, x, y):
    global visited
    queue = deque()
    queue.append( (x, y) )
	
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
			# 주어진 노드의 범위를 벗어나는 경우
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
			# 벽을 만난 경우
            if graph[nx][ny] == 1:
                continue
			# 감염이 가능한 노드들은 2로 바꾸고 visited에 반영
            if graph[nx][ny] == 0:
                visited[nx][ny] = True
                graph[nx][ny] = 2
                queue.append( (nx, ny))

safe_zone = []
#임의의 3개 벽을 추가한 각각의 경우의 수들에 대해서
for comb in wall_comb:
	# 3개의 조합이 달라질때마다 기존의 그래프를 초기화 해야하므로 deep copy
    graph_ = copy.deepcopy(graph)
    for i in range(3):
        x, y = comb[i]
        #벽 추가
        graph_[x][y] = 1

    visited = [[False for i in range(m)] for j in range(n)]
    sum = 0
    for x in range(n):
        for y in range(m):
        	# bfs를 돌릴 조건을 충족하는 경우 : 아직 방문하지 않았으면서 2인 경우
            if not visited[x][y] and graph_[x][y] == 2:
                bfs(graph_, x, y)
	
    #감염이 안된 구역들 누적
    for i in range(n):
        for j in range(m):
            if graph_[i][j] == 0:
                sum += 1

    safe_zone.append(sum)

print(max(safe_zone))

このように书き终わった后にとても耻ずかしいと感じます...
発表するすべての文章を書いた後、他のブログの解答方法を参考にして、方法も論理の流れも似ています!(嬉)これは三星のソフトウェアパワーテストの出題です!これからも頑張ります!