알고리즘/백준
[백준 / Python] 2606번 바이러스 | 초코더
cloud_nice
2020. 1. 17. 23:02
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
www.acmicpc.net
접근법
저는 BFS를 이용해 풀었습니다! 이 링크를 참고하시면 돼요~
다 같은데 다른 점은 이문제에서는 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)