[백준] 2606 : 바이러스 python

 

 

1번 컴퓨터와 자기 사이에 아무리 많은 컴퓨터가 있더라도 연결되어있다면 무조건 바이러스에 걸린다.

따라서 1번 노드에서 BFS를 수행하면서 1번과 연결된 컴퓨터의 개수를 세주면 된다.

 

1. 컴퓨터의 수 n을 입력받는다.

2. 간선의 수 m을 입력받는다.

3. m줄에 걸쳐 그래프의 연결 정보를 입력받고 graph라는 2차원 리스트에 저장한다.

4. 해당 정점을 방문했는지 확인하는 visited 리스트를 만들고 0으로 초기화한다. 방문할 때마다 1로 바꿔주면, BFS를 수행한 뒤에 visited 리스트의 총합-1을 했을 때 1번과 연결된 컴퓨터의 개수를 알 수 있다.

5. dfs 함수를 작성한다.

6. 1번 컴퓨터에서 dfs함수를 수행하고 연결된 컴퓨터의 개수를 출력한다.

 

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
graph=[[]for i in range(n+1)]

for i in range(m):
    s,e = map(int,input().split())
    graph[s].append(e)
    graph[e].append(s)
visited = [0]*(n+1)

def dfs(v):
    visited[v] = 1
    global cnt
    for i in graph[v]:
        if visited[i]==0:
            dfs(i)
            
dfs(1)
print(sum(visited)-1)