2606 - 바이러스 [DFS]

출처 : 백준 2606 바이러스

문제

컴퓨터 노드의 수와 노드들간의 관계에 대한 정보가 주어진다. 1이 최초로 바이러스에 감염된 컴퓨터이고 연결된 네트워크에 따라서 바이러스가 퍼지게 된다. 연결이 되어 있지 않는 노드들은 감염이 되지 않는다. 그렇다면 1번 컴퓨터부터 시작해서 1번을 제외하고 총 몇개의 컴퓨터가 감염되는 지 알아보는 문제이다.

이 문제는 기본 DFS로 풀 수 있는 문제이다. 처음에 노드들간 엣지정보를 받으면 양방향이기 때문에 해당 노드들의 엣지 정보에 추가를 한다. 그런 다음에 1번 부터 시작해서 DFS를 진행하면서 방문한 노드들(바이러스가 퍼진 노드들)을 리스트에 추가를 한다. 마지막에 더 옮겨갈 컴퓨터가 없으면 해당 리스트를 반환한다. [1]이 포함되어 있기 떄문에 해당 리스트의 길이에서 1을 뺀 값을 출력하면 된다.

풀이

# BOJ 2606 - 바이러스
import sys
r = sys.stdin.readline


def dfs(v, egs, ans):
    for i in egs[v]:
        if i not in ans:
            ans.append(i)
            dfs(i, egs, ans)
    return ans


N = int(r())
edges = [[] for _ in range(N+1)]
for _ in range(1, int(r())+1):
    e1, e2 = map(int, r().split())
    edges[e1].append(e2)
    edges[e2].append(e1)

print(len(dfs(1, edges, [1]))-1)