[Python] 백준 2606번: 바이러스

# 문제 내용

백준 2606번: 바이러스

2606번: 바이러스

 

# 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

# 풀이

- 인접리스트 + BFS 

- 처음 풀이 때 인접 리스트로 입력받을 때 무방향그래프인 걸 고려하지 않고 노드 연결 정보가 미비되어 틀렸음

from collections import deque
import sys
input = sys.stdin.readline

# 노드, 컴퓨터 수 (1 <= n <= 100)
n = int(input())

# 엣지, 연결된 컴퓨터 쌍의 수
m = int(input())

# 인접 리스트, 연결 정보 표시
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]

# 결과
result = 0

# 무방향 그래프이므로 양방향 연결
for _ in range(m):
  x, y = map(int, input().split())
  graph[x].append(y)
  graph[y].append(x)

# 1번 컴퓨터부터
q = deque()
q.append(1)
visited[1] = True


while q:
  now = q.popleft()
  result += 1
  
  for node in graph[now]:
    if visited[node] != True:
      q.append(node)
      visited[node] = True

print(result-1)