[백준] 2606 - 바이러스 [Python(파이썬)]

문제

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

2606번: 바이러스

 

풀이

이 문제는 가장 기초적인 그래프 탐색 문제다. 1번 노드부터 시작해서 깊이 우선 탐색을 시작하며, 노드를 방문할 때마다 횟수(cnt)를 1씩 증가시킨다. 문제의 조건에 "1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다."라고 명시되어있으므로 1번 컴퓨터를 제외한 방문 횟수(cnt-1)를 출력하면 된다.

 

코드

import sys
import collections
sys.setrecursionlimit(10**6)

def dfs(v):
    global cnt
    visited[v] = 1
    cnt += 1
    for w in g[v]:
        if not visited[w]:
            dfs(w)

n = int(sys.stdin.readline().strip())
num_of_edges = int(sys.stdin.readline().strip())
g = collections.defaultdict(list)
visited = [0 for _ in range(n+1)]
cnt = 0

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

dfs(1)
print(cnt-1)