백준, 바이러스, 2606, 파이썬

[유형]

DFS

 

[문제링크]

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

 

[요약]

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

 

[문제풀이]

import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().rstrip()

def dfs(v,graph,visited):
    global answer
    visited[v] = 1
    for i in graph[v]:
        if visited[i] == 0:
            answer+=1
            dfs(i,graph,visited)

n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
answer = 0

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

dfs(1,graph,visited)
print(answer)