백준 2606: 바이러스 해설- python

✏️ 문제

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

2606번: 바이러스

 

✏️ 풀이

아이디어는 간단하다. BFS를 이용해 1부터 아래로 쭉 탐색해 리스트에 저장하고 리스트의 길이를 출력했다.

입력데이터의 표현방식은 인접행렬을 이용했다.

from collections import deque

n=int(input())
m=int(input())

# 인접영행렬
matrix = [[0]*(n+1) for i in range(n+1)]
# 입력받는 값에 대해 영형렬에 1삽입(인접리스트생성)
for i in range(m):
  a,b=map(int,input().split())
  matrix[a][b]=matrix[b][a]=1
#bfs 구현
visited=[0]*(n+1)
virus=[]
def bfs(V):
  #방문해야할 곳을 순서대로 넣을 큐
  queue=deque([V])
  visited[V]=1
  
  #큐안에 데이터없을때까지
  while queue:
    V=queue.popleft()
    virus.append(V)
    for i in range(1, n+1):
      if(visited[i]==0 and matrix[V][i]==1):
        queue.append(i)
        visited[i]=1

bfs(1)
print(len(virus)-1)