https://www.acmicpc.net/problem/14502
14502번: 연구소인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크www.acmicpc.net
브루트포스
모든 blank에 대하여, 길이가 3인 comb를만들고,
각각의 경우에대해 bfs를수행하여 0이 최대인값을 구한다.
지금까지 copy가 만능인줄알았는데, 아니였다.
copy를 쓰면, 그 객체 자체의 주소값은은 다르지만,
다차원배열인경우, 그 안의 배열의 주소값은 같다.
#ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 왜일케만들었지
따라서, copy모듈의 decopy()를 사용하여 깊은복사를 해야만, 독립적인 arr을 유지할 수 있다.
이것때문에 한참고민했다.
import sysfrom collections import dequefrom itertools import combinations
import copy ##!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!input=sys.stdin.readline
move=[[-1,0],[1,0],[0,-1],[0,1]]answer=0def bfs(walls): global answer
tmp_arr=copy.deepcopy(arr) !!!!!!!!!!!!!!!!!!!!!!!!!
tmp_answer=len(blank_list) for i,j in walls: tmp_arr[i][j]=1
tmp_answer-=1 que=deque() que.extend(virus_list) while que:
i,j=que.popleft() for a,b in move: tmp_i,tmp_j=i+a,j+b
if 0<=tmp_i<n and 0<=tmp_j<m and tmp_arr[tmp_i][tmp_j]==0:
tmp_arr[tmp_i][tmp_j]=2 tmp_answer-=1
que.append((tmp_i,tmp_j)) answer=max(answer,tmp_answer)
n,m=map(int,input().split())arr=[]virus_list=[]blank_list=[]
for i in range(n): tmp=[* map(int,input().split())] arr.append(tmp)
for j in range(len(tmp)): if tmp[j]==2:
virus_list.append((i,j)) elif tmp[j]==0:
blank_list.append((i,j))wall_comb=list(combinations(blank_list,3))
for walls in wall_comb: bfs(walls)print(answer)