백준 : 바이러스 - 2606

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

예제 입력 1 

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1 

4

 

from collections import deque
import sys


c_node = int(input())
c_edge = int(input())

# 인접 리스트, 1번부터 N번까지 사용하기 위해 N+1 크기로 초기화
graph = [[] for _ in range(c_node + 1)]

# 방문 여부를 체크하는 배열을 N+1 크기로 초기화
visited = [False] * (c_node+1)

for _ in range(c_edge):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)


def bfs(start_node):
    count = 0
    queue = deque([start_node])

    visited[start_node] = True

    while queue:
        v = queue.popleft()

        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
                count +=1

    return count

print(bfs(1))

주어진 코드는 너비 우선 탐색(BFS) 알고리즘을 사용하여 네트워크에서 바이러스에 감염되는 컴퓨터의 총 수를 계산하는 문제임.

 

BFS 함수는 탐색의 시작점인 1번 컴퓨터부터 시작하여 연결된 모든 컴퓨터를 순차적으로 방문해야 하고 방문하지 않은 새로운 컴퓨터를 발견할 때마다 count 변수를 하나씩 늘려 감염된 컴퓨터 수를 세는 것이 중요함.

큐에 더 이상 탐색할 컴퓨터가 남아있지 않으면 탐색을 종료하고, 1번 컴퓨터를 제외한 감염된 컴퓨터의 총수인 count 값을 반환하도록 하게 했다. 이때 입력 받는 값이 각 노드와 노드를 이어주는 것을 알려주기 위해서 각 그래프의 위치별로 서로 이어주도록 진행하였다.