백준 / 14502 / 연구소 / python

from collections import deque

direction = [[1,0], [-1,0], [0,1], [0,-1]]

def virus():
    maps_copy = []

    for i in range(n):
        maps_copy.append(maps[i][:])
    
    for vx, vy in virus_where:
        q = deque([[vx, vy]])

        while q:
            x, y = q.popleft()

            for d in direction:
                nx, ny = x + d[0], y + d[1]

                if 0 <= nx < n and 0 <= ny < m and maps_copy[nx][ny] == 0:
                    maps_copy[nx][ny] = 2
                    q.append([nx, ny])
    
    cnt = 0
    for i in range(n):
        cnt += maps_copy[i].count(0)
    
    return cnt

def dfs(deph):
    global result
    if deph == 3:
        result = max(result, virus())
        return
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 0:
                maps[i][j] = 1
                dfs(deph+1)
                maps[i][j] = 0


n, m = map(int, input().split())
maps = [[0] * m for _ in range(n)]
visited = [[False]*m for _ in range(n)]
virus_where = []
for i in range(n):
    s = list(map(int, input().split()))
    for j in range(m):
        maps[i][j] = s[j]
        if s[j] == 2:
            virus_where.append([i,j])

result = 0
dfs(0)

print(result)

우선 벽 3개를 세우기 위한 dfs 진행 벽 3개의 경우 주어지는 연구소 크기가 크지 않으므로 완전 탐색으로 진행이 가능하다.

dfs를 통해 벽 3개를 세웠다면 이제 bfs를 통해 바이러스를 감염시키고 0의 갯수를 센다.

bfs와 dfs를 잘 이해하고 있다면 어럽지 않은 문제

---

maps_copy = []

for i in range(n):
	maps_copy.append(maps[i])

처음에 virus 부분에서 위와 같이 copy했었다. 이렇게 하면 가능하다고 판단했지만 위 코드도 light copy이다. 그래서 처음 코드와 같이 수정

리스트 복사에 대해서 다시 한 번 생각하게 해준 문제!