[백준 / Python] 2606번 바이러스 | 초코더

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

2606번: 바이러스

 

접근법

저는 BFS를 이용해 풀었습니다! 이 링크를 참고하시면 돼요~

https://sinsomi.tistory.com/entry/%EB%B0%B1%EC%A4%80-Python-1260%EB%B2%88-DFS%EC%99%80-BFS-%EC%B4%88%EC%BD%94%EB%8D%94

 

다 같은데 다른 점은 이문제에서는 1번 컴퓨터가 바이러스가 걸렸을때 바이러스가 걸리게 되는 경로를 반환하는 것이 아닌 바이러스가 걸린 컴퓨터의 갯수를 구해주라고 하였으니 찾은 경로에다가 len()함수를 써주시고 1번 컴퓨터는 빼줘야 하므로 -1을 해주시면 됩니다.

 

나의 풀이

N = int(input())
M = int(input())
V = 1
matrix = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    link = list(map(int, input().split()))
    matrix[link[0]][link[1]] = 1
    matrix[link[1]][link[0]] = 1

def dfs(current_node,matrix,foot_prints):
    foot_prints += [current_node]
    for search_node in range(len(matrix[current_node])):
        if matrix[current_node][search_node] and search_node not in foot_prints:
            foot_prints = dfs(search_node,matrix,foot_prints)
    return foot_prints

count=dfs(V,matrix,[])
print(len(count)-1)