백준 2606 바이러스 파이썬

백준 2606 바이러스 풀이

접근방식

1. 큐 자료구조를 이용한다.
2. 우선 각 노드의 간선을 리스트에 저장해준다.
3. BFS 함수를 만든다.
4. 이때, 큐에 시작 노드(1번)을 넣어둔 뒤, for 문을 돌려서 1번과 연결된 노드들을
   탐색해준다.
5. while queue문을 활용하여, queue가 빌 때까지 실행해준다.

# 입력받기
import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

n = int(input())

m = int(input())

graph = [[] for _ in range(n+1)]

for i in range(1, m+1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

ans = 0
visited = [False] * (n+1)
def bfs(start):
    global ans
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                ans += 1
    return ans

print(bfs(1))

해당 문제는 실버3레벨에 해당하므로 어렵지 않게 풀 수 있는 문제였습니다.

BFS 알고리즘을 처음 접하기에 적합한 문제라고 생각합니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다. Just do it & Keep steady