2606_바이러스

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

2606번: 바이러스

 

 

 

이전글에서 사용한 bfs를 활용해서 풀어봤다.

 

어차피 연결된 모든 노드를 다 돌아야하기 때문에 bfs가 더 효율적일것이라 생각해봤다.

 

문제를 해결한 후에 검색해보니 실제로 두 방식의 차이는 크게 없다고 한다 ㅎㅎ.. 좀 더 공부하니 이렇게 모든 경우를 탐색해야하는경우는 dfs가 약간 더 빠르다고 하니 알아두면 좋을 것 같다.

 

from collections import deque

c = int(input())
t = int(input())

graph = [ [] for _ in range(c+1)]
count = 0

for i in range(t):
    s,e = map(int,input().split())
    graph[s].append(e)
    graph[e].append(s)

for i in range(c+1):
    graph[i].sort()

visited = [ False for _ in range(c+1)]


def bfs(s):
    global count
    que = deque([s])
    visited[s] = True
    while que:
        tmp = que.popleft()
        for i in graph[tmp]:
            if not visited[i]:
                que.append(i)
                visited[i] = True
                count+=1

bfs(1)
print(count)