## 연구소
from collections import deque
from itertools import combinations
import copy
n,m = map(int, input().split())
maps=[]
for i in range(n):
k=list(map(int, input().split()))
maps.append(k)
dx=[1, -1, 0, 0]
dy=[0, 0, 1, -1]
def bfs(mm):
ans=0
q=deque()
# 바이러스가 퍼져나가면 나오는 결과
for i in range(n):
for j in range(m):
if tmp[i][j]==2:
q.append((i, j))
while q:
x, y = q.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx<0 or nx>=len(mm) or ny<0 or ny>=len(mm[0]):
continue
if mm[nx][ny]==1 or mm[nx][ny]==2:
continue
if mm[nx][ny]==0:
q.append((nx, ny))
mm[nx][ny]=2
for i in range(n):
for j in range(m):
if mm[i][j]==0:
ans+=1
return ans
#벽을 3개 세워야 함.
root=[]
for i in range(n):
for j in range(m):
if maps[i][j]==0:
root.append((i, j))
answer=0
for k in list(combinations(root, 3)):
tmp=copy.deepcopy(maps)
for i in range(3):
tmp[k[i][0]][k[i][1]]=1
answer=max(answer,bfs(tmp))
print(answer)
처음에는 아래와 같이 코드를 작성했다.
이 코드의 문제는 일단 조합에 맞춰서 1이라는 벽을 3개 만들어 준 뒤 바이러스의 위치를 찾아서 bfs()를 진행하는 것이 내가 작성하고자 하는 것이었지만, 이렇게 되면, 바이러스가 bfs로 인해 퍼져가면서 2인 바이러스 위치가 점점 많아지는 그 위치 값들을 다시 bfs로 돌아간다는 것이었다.
그렇다고 조합에 맞춰서 벽을 셋팅해놓은 값을 두고 for문을 밖으로 뺄 수도 없는 것이 for k in list(...)이 돌아가면서 벽을 만들어주기 때문이다..
알고보니 바이러스의 위치를 확인해서 그 값으로 시작하게 하는 부분은 bfs()함수 내에서 하는 것이었다.
그 부분만 bfs()에 넣고 돌리니 바로 해결되었다..!
for k in list(combinations(root, 3)):
tmp=copy.deepcopy(maps)
# print(k)
for i in range(3):
tmp[k[i][0]][k[i][1]]=1
# print(tmp)
# 바이러스가 퍼져나가면 나오는 결과
for i in range(n):
for j in range(m):
if tmp[i][j]==2:
# print("바이러스 개수")
print(tmp)
answer=max(answer,bfs(tmp, i, j))
문제를 보고 설마 무식하게 하는 것일까... bfs로 푸는 건 맞을 것 같은데 벽을 어떻게 세우지 라는 생각에 대해 완전탐색은 아니지 않을까 생각만 하고 실제로 코드 작성을 주저했는데 정말 완전탐색을 사용하는 문제였다.. 항상 완전탐색 문제느 시간초과가 걸릴까봐 코드 작성이 꺼려지는데... 꼭 다음에는 주저않고 일단 해보자라는 마음을 다시 갖고 해보도록 하자!!!