[백준] Python 2606 바이러스 BFS/DFS로 풀이.

먼저 DFS 풀이. 

방문한 노드면 재귀 종료.

방문 안한 노드면 방문처리 해주고 연결된 노드들 확인.

from collections import defaultdict

n = int(input())
connect_len = int(input())

dic = defaultdict(list)
for i in range(connect_len):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a) # 양방향

# dfs 접근

visited = [False for _ in range(n+1)] # 1번부터 시작하기 위해 n+1
def dfs(v, visited):
    global cnt
    if visited[v]:
        return

    visited[v] = True
    for k in dic[v]:
        if not visited[k]:
            dfs(k, visited)


dfs(1, visited)
print(visited.count(True)-1)

BFS풀이. queue를 활용하여 근처에있는 노드들 순차적으로 확인.

from collections import defaultdict
from collections import deque

n = int(input())
connect_len = int(input())

dic = defaultdict(list)
for i in range(connect_len):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a) # 양방향

# bfs 접근

visited = [False for _ in range(n+1)] # 1번부터 시작하기 위해 n+1

q = deque()
q.append(1)

while q:
    v = q.popleft()

    visited[v] = True

    for k in dic[v]:
        if not visited[k]:
            q.append(k)

print(visited.count(True)-1)