[백준/Python] 2606. 바이러스

※ 문제

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

 

※ 문제 유형

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색(SILVER_3)

※ 나의 풀이

• 인접 리스트를 통한 그래프 생성
• BFS(너비 우선 탐색)

import sys
from collections import deque

N = int(sys.stdin.readline()) # 정점(Vertex)(노드) 수
M = int(sys.stdin.readline()) # 입력 그래프 쌍 수

graph = { i :[] for i in range(N + 1) }
# print(graph) # {0: [], 1: [], 2: [], 3: [], 4: [], 5: [], 6: [], 7: []}


for i in range(M):
    vertex_1, vertex_2 = map(int, sys.stdin.readline().split())

    # 양방향 그래프
    graph[vertex_1].append(vertex_2)
    graph[vertex_2].append(vertex_1)

# print(graph) # {0: [], 1: [2, 5], 2: [1, 3, 5], 3: [2], 4: [7], 5: [1, 2, 6], 6: [5], 7: [4]}

visited = [False] * (N + 1)
ans = 0

# BFS : 너비 우선 탐색 (1 - 2 - 5 - 3 - 6)
def BFS(x): # x번 부터 BFS 실행
    que = deque()
    global ans # 감연된 컴퓨터 수
    que.append(x)
    visited[x] = True

    while que:
        n = que.popleft()
        for n_next in graph[n]:
            if not visited[n_next]: # 감염이 되지 않았다면
                visited[n_next] = True # 감염
                que.append(n_next) # 감염 리스트 추가
                ans += 1 # 감염된 컴퓨터 수 1 증가

BFS(1) # 1번에서 BFS 실행
# print(visited) [False, True, True, True, False, True, True, False]
print(ans)