[백준] 2606번 :바이러스 (python 파이썬)

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

2606번: 바이러스

 

 

import sys
from collections import deque


n = int(input())
m = int(input())
graph = [ []  for i in range(n+1)] # 각각의 컴퓨터마다 연결된 노드 정보
visited = [ False for i in range(n+1)] # 방문 여부
for i in range(m): # 그래프에 경로 입력하기
    a,b = map(int, sys.stdin.readline().rstrip().split(" "))
    graph[a].append(b)
    graph[b].append(a)

# 결과 [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]] 1번은 2,5번과 연결, 2번은 1,3,5번과 연결......



q = deque([1]) # 1번 컴퓨터부터 시작 [현재 위치 = 1]
visited[1] = True
ans = 0
while q: # 경로 따라가며 지나간 길 표시 및 정답 세기 [q에 아무것도 없을 때까지]
    now = q.popleft() # 현재 위치를 꺼내면서 제거
    for i in graph[now]: # 현재 위치의 연결 노드를 훑으면서 방문하지 않은 부분 q에 추가 및 방문 표시
        if visited[i] == False: # 방문하지 않으면
            visited[i] = True # 방문 표시 후
            q.append(i) # q에 추가
            ans = ans+1 # 개수 추가
print(ans)

 

 

입력의 첫줄에는 총 컴퓨터의 개수, 둘째 줄에는 연결된 짝의 개수이다.

 

셋째 줄 부터는 연결된 짝의 정보가 입력된다.

 

따라서

1. 모든 컴퓨터의 각각의 경우마다 연결된 컴퓨터의 정보를 리스트에 넣는다.

2. 첫 번째 컴퓨터부터 차례대로 따라가면서 방문 여부를 체크를 한다. (+ 정답 개수 더하기)

3. 더이상 새롭게 방문할 컴퓨터가 없을 때까지 2를 반복한다.