백준 알고리즘 2606번 바이러스(python)

기본적인 DFS & BFS 문제이다.

양방향임 구조임에 주의하자. 처음에 단방향으로 만들어 놓고 풀려해서 왜 틀렸는지 한참을 찾았다. 

DFS 풀이

def dfs(node):
    if check[node] == 0:
        check[node] = 1
        for t in graph[node]:
            dfs(t)

N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(int(input())):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
check = [0]*(N+1)
dfs(1)
print(sum(check)-1)

BFS 풀이

from collections import deque

def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        node = queue.popleft()
        if check[node] == 0:
            check[node] = 1
            for t in graph[node]:
                queue.append(t)

N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(int(input())):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
check = [0]*(N+1)
bfs(1)
print(sum(check)-1)