백준 14502 연구소

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

14502번: 연구소

브루트포스

모든 blank에 대하여, 길이가 3인 comb를만들고,

각각의 경우에대해 bfs를수행하여 0이 최대인값을 구한다.

 

지금까지 copy가 만능인줄알았는데, 아니였다.

copy를 쓰면, 그 객체 자체의 주소값은은 다르지만, 

다차원배열인경우, 그 안의 배열의 주소값은 같다. 

#ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 왜일케만들었지

따라서, copy모듈의 decopy()를 사용하여 깊은복사를 해야만, 독립적인 arr을 유지할 수 있다.

이것때문에 한참고민했다.

 

import sys
from collections import deque
from itertools import combinations
import copy ##!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
input=sys.stdin.readline
move=[[-1,0],[1,0],[0,-1],[0,1]]
answer=0
def 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)