알고리즘/백준 문제풀이
[백준] 2606번 :바이러스 (python 파이썬)
매일_공부
2022. 12. 31. 08:25
반응형
https://www.acmicpc.net/problem/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를 반복한다.
반응형