[ BOJ 2606 ] 바이러스(Python)

문제

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

1번 컴퓨터와 연결된 컴퓨터의 수를 구하는 문제이다.
dfs를 이용해서 간단하게 풀 수 있다.

문제 풀이

1. 양방향으로 그래프를 만들어준다.
2. 해당 노드를 방문한 적이 없으면 방문했다고 체크해준 뒤에,
   노드와 연결된 다른 노드를 dfs 함수로 넣어준다.
3. 방문 체크를 한 노드의 개수를 세어주고, 1번 노드는 제외해야 하니 1을 빼준다.

코드

import sys

computer = int(sys.stdin.readline().rstrip())
connect = int(sys.stdin.readline().rstrip())
visited = [0] * (computer + 1)
total = 0
graph = {}

for i in range(connect):
    key, value = map(int,sys.stdin.readline().rstrip().rsplit())

    #양방향으로 그래프 만들어주기
    if key not in graph:
        graph[key]=[value]
    else:
        graph[key].append(value)

    if value not in graph:
        graph[value]=[key]
    else:
        graph[value].append(key)

def dfs(index):
    #방문한 적 없으면
    if visited[index] == 0:
        visited[index] = 1

        while(graph[index]):
            dfs(graph[index].pop(0))

dfs(1)

for num in visited:
    if num==1: total += 1

print(total-1)