백준 2606번 바이러스

DFS,BFS를 이용한 문제 풀이 바이러스에 감염된 컴퓨터에 연결된 컴퓨터를 모두 찾아서 그 숫자를 세면된다 DFS나 BFS중 가중치를 1로 계산해서 마지막 가중치에서 처음 감염된 컴퓨터를 빼줌 (-1) 그러면 감염된 컴퓨터의 총 개수가 나온다

너비 우선탐색 (BFS)

#bfs 풀이
from collections import deque
import sys
input = sys.stdin.readline

#방문했으면 카운팅-> 감염된 컴퓨터

computer_num = int(input()) #컴퓨터 개수 입력
line = int(input()) # 간선 개수를 입력

line_list = [[] for _ in range(computer_num+1)] #간선의 정보가 들어갈 리스트
ans = [0]*(computer_num+1) 
cnt = 1 # 순서 카운팅을 위한것
ans[1]=cnt #방문순서를 저장한다
q = deque([1]) 



for _ in range(0,line):
	a,b = map(int,input().split())
	line_list[a].append(b)
	line_list[b].append(a)
	


for i in line_list:
	i.sort()

while q:
    t = q.popleft()
    for i in line_list[t]:
        if ans[i]:
            continue
        cnt += 1
        ans[i] = cnt
        q.append(i)

print(cnt-1)

---

깊이 우선탐색(DFS)

#dfs 풀이
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) #RecursionError해결

def dfs(k): #재귀가 일어나면서 수직을 탐색을 한다
    global cnt
    ans[k] = cnt
    for i in line_list[k]:
        if ans[i]:
            continue
        cnt += 1
        dfs(i)

computer_num = int(input()) #컴퓨터 개수 입력
line = int(input()) # 간선 개수를 입력

line_list = [[] for _ in range(computer_num+1)] #간선의 정보가 들어갈 리스트
ans = [0]*(computer_num+1) #각 노드의 방문 순서가 저장되는 공간
cnt = 1 # 순서 카운팅을 위한것


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

dfs(1)#시작이 1부터 시작하기 때문에

print(cnt-1)