[BOJ] 2606번 : 바이러스 - 파이썬(Python)

문제 해석

---

이 문제는 1을 시작노드로 하여 방문할 수 있는 노드의 수를 모두 구하는 탐색 문제이다.

 

문제 풀이

---

DFS나 BFS를 구현할 수 있다면 별다른 문제없이 그 자체로 해결되는 문제이며 BFS를 이용해서 풀었다.

 

import sys
from collections import deque

N = int(sys.stdin.readline().rstrip())

M = int(sys.stdin.readline().rstrip())


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


for _ in range(M):
    v1, v2 = map(int, sys.stdin.readline().split())
    graph[v1].append(v2)
    graph[v2].append(v1)


cnt = 0

visited = [False for _ in range(N + 1)]

deq = deque()

# 1번 노드에서 출발한다
deq.append(1)

while deq:
    x = deq.popleft()
    visited[x] = True
    for y in graph[x]:
        if visited[y] == False:
            deq.append(y)
            visited[y] = True
            cnt += 1
print(cnt)

 

1을 제외한 노드중에 방문할 수 있지만 아직 방문하지 않은 노드를 방문처리를 할 때 cnt를 증가시킴으로써

 

이 문제에서 제시한 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 구할 수 있다.