백준 2606번: 바이러스

2606번: 바이러스

문제 해설

• 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. (그래프 문제)
• 첫째 줄에는 컴퓨터의 수 (컴퓨터의 수는 100 이하)
• 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수

문제 풀이

• DFS vs BFS : BFS가 속도면에서 더 빠를거라고 예상, 굳이 DFS로 안풀어도 됨 (DFS로 안 풀어도 된다면 더 빠른 BFS로 풀자!)
• BFS: 항상 DEQUE 생각 -> popleft() 하여, deque에 더 높은 level의 노드를 추가, 이때 거리같은 조건이 들어가면 추가해줌!
• visited list: 노드보다 N+1 설정, 노드의 네이밍에 따라 달라지지만 보통 노드는 1부터 시작하므로 (N+1) 공간 만들어줄 것
• Graph: 양방향그래프! 항상 서로 연결해주기

from collections import deque, defaultdict

def bfs(graph,start,visited):
    visited[start] = True

    new_computer = deque([start])

    while new_computer:
        computers = new_computer.popleft()

        for computer in graph[computers]:
            if not visited[computer]:
                new_computer.append(computer)
                visited[computer] = True

N = int(input())
M = int(input())
visited = [False] * (N+1)

graph = defaultdict(list)
for _ in range(M):
    i,j = list(map(int,input().split()))
    graph[i].append(j)
    graph[j].append(i)

bfs(graph,1,visited)
print(sum(visited)-1)