문제 출처 : https://www.acmicpc.net/problem/1260
난이도 : 실버 2

문제 파악

DFS와 BFS를 한번에 써볼 수 있는 문제이다.

무방향 인접리스트 그래프를 입력을 받고
DFS,BFS 에 대한 visited, order 배열을 따로 입력받은 후 DFS,BFS를 구현해주면 된다.

해답 코드

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

N, M, start = map(int,input().split())

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

for _ in range(M):
    u, v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)
# [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]]

for i in range(1,N+1):
    graph[i].sort()

visited_DFS = [None] + [False]* (N)
visited_BFS = [None] + [False] * (N)
# [None, False, False, False, False]

order_DFS = []
order_BFS = []

# DFS
def DFS(u):
    visited_DFS[u] = True
    order_DFS.append(u)

    for node in graph[u]:
        if not visited_DFS[node]:
            DFS(node)

# BFS
def BFS(u):
    visited_BFS[u] = True
    queue = deque([u])

    while queue:
        node = queue.popleft()
        order_BFS.append(node)
        for neighbor in graph[node]:
            if not visited_BFS[neighbor]:
                visited_BFS[neighbor] = True
                queue.append(neighbor)


DFS(start)
BFS(start)

print(*order_DFS)
print(*order_BFS)