[Python] 백준 #2606 바이러스 - bfs

문제

2606번: 바이러스

 

풀이

인접리스트 adj와 visited 배열을 통해 bfs로 풀었다.  

마지막에 1을 빼준건 1번 컴퓨터를 제외하기 위함

import sys
from collections import deque

# N: 노드 수 / M: 엣지 수
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

# 인접 리스트
adj = [[] for _ in range(N)]
visited = [0 for _ in range(N)]

# 인접 리스트 채우기
for _ in range(M):
    x, y = map(int, sys.stdin.readline().split(" "))
    adj[x-1].append(y-1)
    adj[y-1].append(x-1)

queue = deque()
queue.append(0)  # 1번 컴퓨터
visited[0] = 1
count = 0

# bfs
while queue:
    v = queue.popleft()
    count += 1

    # v와 인접한 모든 애들
    for each in adj[v]:
        if visited[each] == 0:
            queue.append(each)
            visited[each] = 1

print(count-1)