[BaekJoon Online Judge] 2606 – 바이러스

문제

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

소스코드

dfs 를 이용해서 문제를 해결한다. 양방향 간선으로 표현된 네트워크 입력을 그래프로 표현한 뒤 1번 컴퓨터부터 탐색을 시작하면 바이러스에 감염되는 모든 컴퓨터를 찾아낼 수 있다.

N = int(input())
V = int(input())
graph = [[0 for _ in range(N)] for _ in range(N)]
for i in range(V):
    a,b = map(int,input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

stack = [0]
polluted = []
while stack:
    curr = stack.pop(0)
    polluted.append(curr)
    for i in range(N):
        if graph[curr][i] == 1 and i not in polluted:
            stack.append(i)

print(len(set(polluted))-1)