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

DFS 풀이

n = int(input())
m = int(input())
matrix = [[0]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    matrix[a][b] = matrix[b][a] = 1

visited = [0] * (n+1)
def dfs(v):
    
    visited[v] = 1
    for i in range(1, n+1):
        if visited[i]==0 and matrix[v][i] == 1:
            dfs(i)

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

BFS 풀이

from collections import deque
import sys

n = int(input())
m = int(input())
graph = [[0]*(n+1) for i in range(n+1)]

for i in range(m):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1
visited = [0] * (n+1)

def bfs(v):
    
    queue = deque()
    queue.append(v)
    visited[v] = 1
    while queue:
        v = queue.popleft()
        for i in range(1, n+1):
            if visited[i] == 0 and graph[v][i] == 1:
                queue.append(i)
                visited[i] = 1
    
bfs(1)    
print(visited.count(1)-1)