백준 2606 바이러스 python

문제 링크
https://www.acmicpc.net/problem/2606

DFS와 BFS 문제와 같이
DFS/BFS 연습하기 좋은 문제.

DFS 풀이

def DFS(x):
    global cnt
    visited[x] = True
    for y in adj[x]:
        if visited[y]: continue
        cnt += 1
        DFS(y)

N = int(input())
M = int(input())
adj = [[] for _ in range(N+1)]
cnt = 0
visited = [False] * (N + 1)
for _ in range(M):
    x, y = map(int, input().rstrip().split())
    adj[x].append(y)
    adj[y].append(x)
DFS(1)
print(cnt)

BFS 풀이

import sys
from collections import deque
sys.setrecursionlimit(100000)

def BFS(x):
    queue = deque()
    queue.append(x)
    visited[x] = 1
    while queue:
        x = queue.popleft()
        for y in adj[x]:
            if visited[y]: continue
            visited[y] = 1
            queue.append(y)

N = int(input())
M = int(input())
adj = [[] for _ in range(N+1)]
visited = [0] * (N + 1)
for _ in range(M):
    x, y = map(int, input().rstrip().split())
    adj[x].append(y)
    adj[y].append(x)
BFS(1)
print(sum(visited)-1)