2606번: 바이러스 (그래프, BFS, DFS) - Fastcampus

www.acmicpc.net/problem/2606

2606번: 바이러스

from collections import deque


# BFS-1: 큐에서 꺼내고 방문 마킹
def bfs(start):
    qu = deque([start])
    visited = [0] * len(graph)

    cnt = 0
    while qu:
        node = qu.popleft()

        if not visited[node]:
            visited[node] = 1
            cnt += 1  # 로직
            for e in graph[node]:
                qu.append(e)
    return cnt


# BFS-2: 큐에 추가할때 방문 마킹
def bfs(start):
    qu = deque([start])
    visited = [0] * len(graph)
    visited[start] = 1

    cnt = 0
    while qu:
        node = qu.popleft()

        cnt += 1  # 로직
        for e in graph[node]:
            if not visited[e]:
                visited[e] = 1
                qu.append(e)
    return cnt


# DFS-1: 재귀했을 때 조건검사
def dfs(node, cnt=0):
    if not visited[node]:
        visited[node] = 1
        cnt += 1  # 로직
        for e in graph[node]:
            cnt = dfs(e, cnt)
    return cnt


# DFS-2: (노드에서 방문마킹) 재귀호출 직전에 조건검사
def dfs(node, cnt=0):
    visited[node] = 1
    cnt += 1  # 로직
    for e in graph[node]:
        if not visited[e]:
            cnt = dfs(e, cnt)
    return cnt


N = int(input())
M = int(input())

graph = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)


print(bfs(1)-1)
# visited = [0] * (N+1)
# print(dfs(1)-1)