[DFS] 백준 2606번 바이러스 with Python3

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

2606번: 바이러스

문제

 

내 풀이

def dfs(v):
    visited[v] = 1
    for i in range(1, n + 1):
        if visited[i] == 0 and graph[v][i] == 1:
            # 1. 방문한 적이 없고,
            # 2. 현재 v 노드에서 i노드로 간선이 연결되어있다면
            dfs(i)


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

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

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


dfs(1)
print(visited.count(1) - 1)

해설

첫번째 문제 와 거의 똑같다. 유일하게 다른 점은 1에서 시작해서 감염된 모든 컴퓨터의 개수를 출력하라는 것인데, 1번 컴퓨터를 제외해야하기에 visited 리스트에 1 원소를 세고 1을 빼준 값이 답이다.