[BFS/DFS] 연구소

 

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

 

tep list 를 하나 만들어야 하는데,

tmp = graph 하면, tmp가 변경될 때 참조주소를 복사 하는것이기 때문에 수정 및 삭제에 graph도 같이 변경된다.

 

찾아보니, tmp = list(graph) 이나 tmp=graph.copy() 하면 tmp 값이 변경될 때 graph는 유지 된다고 함.

graph = [0, 0, 0, 0]

tmp = list(graph)
for i in range(len(tmp)):
    tmp[i] = i+1

print(tmp)
print(graph)

#output
#[1, 2, 3, 4]
#[0, 0, 0, 0]

코드가 심플할 때는 영향이 없는 것 같지만, 함수 안에서 리스트 복사용으로 사용하면 영향으로 graph도 값이 변한다.

 

그래서 결국, 

tmp = [[0]*M for _ in range(N)] 으로 graph의 크기만큼 초기화하고,

이중 for 문으로 하나하나 접근해서 값을 다시 지정해준다.

from collections import deque

N,M = map(int, input().split())
graph = []
tmp = [[0]*M for _ in range(N)]
for _ in range(N):
    graph.append(list(map(int, input().split())))

count = 0
virus = []
max_safe = -1e9

for i in range(N):
    for j in range(M):
        if graph[i][j] == 2:
            virus.append((i,j))

dx = [0, 0 ,-1 ,1]
dy = [-1, 1, 0, 0]

def spread_virus():
    q = deque(virus)
    count_zero = 0
    for n in range(N):
        for m in range(M):
            tmp[n][m] = graph[n][m]
    while q:
        x, y = q.popleft()
        for di in range(4):
            nx = x + dx[di]
            ny = y + dy[di]

            if nx>=0 and nx<N and ny>=0 and ny<M and tmp[nx][ny] == 0:
                tmp[nx][ny] = 2
                q.append((nx,ny))
            else:
                continue
    for n in range(N):
        for m in range(M):
            if tmp[n][m] == 0:
                count_zero += 1
    return count_zero

def dfs(count):
    global max_safe
    if count == 3:
        max_safe = max(max_safe, spread_virus())
        return
    else:
        for i in range(N):
            for j in range(M):
                if graph[i][j] == 0:
                    graph[i][j] = 1
                    count += 1
                    dfs(count)
                    graph[i][j] = 0
                    count -=1
        return

dfs(count)
print(max_safe)

spread_virus() 함수도 dfs로 구성해도 되지만, 난 bfs가 편해서..