[BOJ] 2606 | 바이러스

아래 백준 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

BFS를 이용해서 1번 정점에서 갈 수 있는 정점의 개수를 세주면 된다.

정점과 간선 정보를 graph에 저장해주고, 1번 정점에서부터 인접한 정점을 큐에 넣어 큐가 빌 때 까지 방문해주면 된다.

코드

---

import sys
from collections import deque
sys.setrecursionlimit(10**8)

com = int(input())
pair = int(input())

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

for _ in range(pair):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(com+1):
    graph[i].sort()
  
def bfs(graph, r):
    visited = [False] * (com + 1)
    q = deque([r])
    visited[r] = True
    virus = 0

    while q:
        node = q.popleft()
        for v in graph[node]:
            if not visited[v]:
                visited[v] = True
                q.append(v)
                virus += 1                
    return virus

print(bfs(graph, 1))

결과

---