[PS] DFS/BFS: 1260 DFS와 BFS

문제 출처

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

포인트

DFS는 list를 통해 구현
BFS는 queue를 통해 구현

코드

# 1260
import sys

fast_input = sys.stdin.readline


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


# 정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호가 주어진다.
node_cnt, edge_cnt, initial_vertex = map(int, fast_input().split())
# 인접 행렬 생성
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] = adjacency_matrix[node_b][node_a] = 1

# DFS로 탐색시 현재의 node를 출력
def dfs(adjacency_matrix, node_cnt, initial_vertex, visit_mark_list):
    fast_print(initial_vertex)
    visit_mark_list[initial_vertex] = 1
    for _ in range(1, node_cnt + 1):
        if adjacency_matrix[initial_vertex][_] == 1 and visit_mark_list[_] == 0:
            dfs(adjacency_matrix, node_cnt, _, visit_mark_list)

# BFS로 탐색시 현재의 node를 출력
def bfs(adjacency_matrix, node_cnt, initial_vertex, visit_mark_list):
    queue = [initial_vertex]
    visit_mark_list[initial_vertex] = 1
    while queue:
        initial_vertex = queue.pop(0)
        fast_print(initial_vertex)
        for _ in range(1, node_cnt + 1):
            if (visit_mark_list[_] == 0 and adjacency_matrix[initial_vertex][_] == 1):
                queue.append(_)
                visit_mark_list[_] = 1


visit_mark_list = [0] * (node_cnt + 1)
dfs(adjacency_matrix, node_cnt, initial_vertex, visit_mark_list)
sys.stdout.write('\n')
visit_mark_list = [0] * (node_cnt + 1)
bfs(adjacency_matrix, node_cnt, initial_vertex, visit_mark_list)