BOJ 2606번: 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

아이디어:

BFS 혹은 DFS로 그냥 그래프를 탐색하기만 하면 되는 간단한 문제이다.

BFS는 큐를 사용해야 되니까 귀찮아서 DFS로 탐색했다.

이제 조금 DFS를 구현하는 게 익숙해진 것 같다.

 

import sys

N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
graph = [[] for _ in range(N+1)]
visit = [False]*(N+1)

for _ in range(K):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(x):
    cnt = -1 #1번 컴퓨터의 감염은 카운트하지 않으므로
    stack = []
    stack.append(x)
    visit[x] = True
    while (stack):
        n = stack.pop()
        cnt+=1
        for i in graph[n]:
            if (visit[i]==False):
                visit[i] = True
                stack.append(i)
    return cnt
print(dfs(1))

1번 컴퓨터로부터 감염된 컴퓨터의 개수를 세는 것이므로 1번컴퓨터는 감염으로 치지 않는다. 따라서 그냥 cnt의 초깃값을 -1로 주었다.