[python 파이썬] 백준 2606번 바이러스

2606번: 바이러스

 

이 문제는 대표적인 BFS 문제이다. 앞서 푼 1260번에서 사용한 BFS함수를 응용해서 풀었더니 쉽게 풀렸다! 

 

 

n = int(input())
m = int(input())

matrix=[[0]*(n+1) for i in range(n+1)]

for i in range(m):
    a,b = map(int,input().split())
    matrix[a][b]=matrix[b][a]=1

visit_list=[1]*(n+1)

def bfs(v):
    count=0
    queue=[v]
    visit_list[v]=0
    while queue:
        v=queue.pop(0)
        count+=1
        # print(v,end=' ') #
        for i in range(1,n+1):
            if(visit_list[i]==1 and matrix[v][i]==1):
                queue.append(i)
                visit_list[i]=0
    return count-1

print(bfs(1))

 

 

 

참고

[python 파이썬] 백준 1260번 DFS와 BFS