[Python] 114502 연구소 - 골드4

문제

해당 문제 링크

정답

## 연구소
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로 푸는 건 맞을 것 같은데 벽을 어떻게 세우지 라는 생각에 대해 완전탐색은 아니지 않을까 생각만 하고 실제로 코드 작성을 주저했는데 정말 완전탐색을 사용하는 문제였다.. 항상 완전탐색 문제느 시간초과가 걸릴까봐 코드 작성이 꺼려지는데... 꼭 다음에는 주저않고 일단 해보자라는 마음을 다시 갖고 해보도록 하자!!!