[BOJ] DFS/BFS - 2606 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

 

[DFS]

 

import sys

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)

for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(vertex):
    # 현재 노드 방문
    visited[vertex] = True

    # 방문하지 않은 인접 노드 방문
    for v in graph[vertex]:
        if not visited[v]:
            visited[v] = True
            dfs(v)


dfs(1)

# 1번을 통해 바이러스 걸린 컴퓨터 출력 (즉, 1번 컴퓨터는 제외)
print(visited.count(True) - 1)

 

[BFS]

 

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)

for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)


def bfs(start):
    queue = deque()
    # 현재 노드 방문
    queue.append(start)
    visited[start] = True

    while queue:
        now = queue.popleft()

        # 방문하지 않은 인접 노드 방문
        for v in graph[now]:
            if not visited[v]:
                queue.append(v)
                visited[v] = True


bfs(1)

# 1번을 통해 바이러스 걸린 컴퓨터 출력 (즉, 1번 컴퓨터는 제외)
print(visited.count(True) - 1)