[PS] DFS/BFS: 2606 바이러스

문제 출처

https://www.acmicpc.net/problem/2606

포인트

DFS와 BFS의 구현

코드

import sys

fast_input = sys.stdin.readline

def fast_print(v):
    sys.stdout.write(str(v) + " ")

node_cnt = int(fast_input())
edge_cnt = int(fast_input())
initial_vertex = 1

adjacency_matrix = [[0] * (node_cnt + 1) for _ in range(node_cnt + 1)]
for _ in range(edge_cnt):
    node_a, node_b = map(int, fast_input().split())
    adjacency_matrix[node_a][node_b] = 1
    adjacency_matrix[node_b][node_a] = 1

def dfs(adjacency_matrix, node_cnt, initial_vertex, visit_mark_list):
    visit_mark_list[initial_vertex] = 1
    child_count = 0
    for _ in range(1, node_cnt + 1):
        if adjacency_matrix[initial_vertex][_] == 1 and visit_mark_list[_] == 0:
            child_count += 1
            child_count += dfs(adjacency_matrix, node_cnt, _, visit_mark_list)
    return child_count

visit_mark_list = [0] * (node_cnt + 1)
dfs_child_count = dfs(adjacency_matrix, node_cnt, initial_vertex, visit_mark_list)
sys.stdout.write(f'{dfs_child_count}')
# def bfs(adjacency_matrix, node_cnt, initial_vertex, visit_mark_list):
#     queue = [initial_vertex]
#     visit_mark_list[initial_vertex] = 1
#     child_count = 0
#     while queue:
#         current_vertex = queue.pop(0)
#         for _ in range(1, node_cnt + 1):
#             if visit_mark_list[_] == 0 and adjacency_matrix[current_vertex][_] == 1:
#                 queue.append(_)
#                 visit_mark_list[_] = 1
#                 child_count += 1
#     return child_count

# visit_mark_list = [0] * (node_cnt + 1)
# bfs_child_count = bfs(adjacency_matrix, node_cnt, initial_vertex, visit_mark_list)
# sys.stdout.write(f'{bfs_child_count}')