[백준][Python] 2606번 바이러스

2606번: 바이러스

 

 

코드

from collections import defaultdict

def dfs(s):
	global cnt
	v.add(s)
	for i in virus[s]:
		if i not in v:
			cnt += 1
			dfs(i)

cnt = 0
com = int(input())
conn = int(input())
virus = defaultdict(list)
v = set()
for i in range(conn):
	a,b = map(int,input().split())	
	virus[a].append(b)
	virus[b].append(a)

dfs(1)
print(cnt)

 

설명

virus라는 딕셔너리에 서로 연결된 컴퓨터 번호를 저장하였다.

dfs를 이용하여 연결된 모든 컴퓨터 번호를 찾았다. set을 이용해서 방문 여부를 확인했다. 아직 방문하지 않았다면 cnt를 1 증가시키고 dfs를 반복했다.