BOJ 1260 - DFS와 BFS

문제

백준 온라인 저지 - 1260번

풀이 과정

DFS 와 BFS 연산을 구현하는 간단한 문제입니다.
먼저 입력으로 받은 간선 정보로 그래프를 생성하고 이후 DFS 와 BFS 함수를 통해 탐색을 수행합니다.

코드

import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)


def bfs(graph, start):
    q = deque()
    visit = [0] * (N + 1)
    order = []

    q.append(start)
    visit[start] = 1

    while q:
        here = q.popleft()
        order.append(here)

        for there in sorted(graph[here]):
            if not visit[there]:
                visit[there] = 1
                q.append(there)

    return order


def dfs(graph, here, visit, result):
    visit[here] = 1
    result.append(here)

    for there in sorted(graph[here]):
        if not visit[there]:
            dfs(graph, there, visit, result)


def make_graph():
    graph = [[] for _ in range(N + 1)]

    for frm, to in edges:
        graph[frm].append(to)
        graph[to].append(frm)

    return graph


def solution():
    graph = make_graph()

    dfs_visit = [0] * (N + 1)
    dfs_result = []
    dfs(graph, V, dfs_visit, dfs_result)
    print(*dfs_result)

    bfs_result = bfs(graph, V)
    print(*bfs_result)


if __name__ == '__main__':
    N, M, V = list(map(int, sys.stdin.readline().split()))
    edges = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

    solution()