[파이썬, Python] 백준 2606: 바이러스

문제

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

2606번: 바이러스

코드

import sys
input = sys.stdin.readline

c = int(input())
n = int(input())

visited = [False for _ in range(c + 1)]
graph = [[]for _ in range(c + 1)]

for _ in range(n):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in graph:
    i.sort()

def dfs(i):
    visited[i] = True
    for i in graph[i]:
        if visited[i] == False:
            dfs(i)
dfs(1)

print(visited.count(True)-1)

설명

우선 컴퓨터의 개수와 연결되어 있는 컴퓨터의 쌍의 개수를 입력받는다.

이후 False로 이루어진 방문 리스트를 컴퓨터의 개수보다 1개 많게 만들어준다.(인덱스를 1부터 세기 위함)
각 컴퓨터가 연결된 리스트를 담은 그래프를 입력받기 위해 공백 리스트를 가진 그래프를 컴퓨터의 개수보다 1개 많게 만들어준다.

각 그래프의 연결관계를 나타내주는 작업을 해준다.
이후 이 그래프를 정렬한다.

dfs를 정의해 준다.
dfs를 진행하며 i를 방문했다면,
i의 방문 리스트를 True로 바꿔주고, i의 하위 그래프 중 False인 그래프에 대하여 dfs를 재귀의 형태로 진행한다.

1번 컴퓨터가 시작점이기에 dfs(1)을 실행해 준다.

이후 방문 리스트의 True인 개수에서 1개를 뺀 수를 출력해 준다.(1번 컴퓨터 제외)