[백준] 1260 DFS와 BFS

import sys
input = sys.stdin.readline
from collections import deque

# dfs(재귀), bfs(큐) 로 구현
n, m, r = map(int, input().split()) 
graph = [ [] for _ in range(n+1)]
visited_dfs = [0] * (n+1)
visited_bfs = [0] * (n+1)

ans_dfs = []
ans_bfs = []
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for lst in graph:
    lst.sort()

#dfs(재귀)
def dfs(graph, r, visited_dfs):
    ans_dfs.append(r)
    visited_dfs[r] = True
    for i in graph[r]:
        if visited_dfs[i] == 0:
            dfs(graph, i, visited_dfs)

#bfs(큐)
def bfs(graph, r, visited_bfs):
    queue = deque()
    # 시작 노드 큐에 삽입 & 방문 처리
    queue.append(r)
    visited_bfs[r] = True
    while queue:
        v = queue.popleft()
        ans_bfs.append(v)
        for i in graph[v]:
            if visited_bfs[i] == 0:
                queue.append(i)
                visited_bfs[i] = True
# 실행
dfs(graph, r, visited_dfs)
bfs(graph, r, visited_bfs)
# 결과 출력
for val in ans_dfs:
    print(val, end=' ')
print()
for val in ans_bfs:
    print(val, end=' ')