1260번: DFS와 BFS (그래프, BFS, DFS) - Fastcampus

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

from collections import deque


# BFS-1: 큐에서 꺼내고 방문 마킹
def bfs(start):
    queue = deque([start])
    visited = [0] * len(graph)

    res = []
    while queue:
        node = queue.popleft()

        if not visited[node]:
            visited[node] = 1
            res.append(node)  # 로직
            for e in graph[node]:
                queue.append(e)
    return res


# BFS-2: 큐에 추가할때 방문 마킹
def bfs2(start):
    queue = deque([start])
    visited = [0] * len(graph)
    visited[start] = 1  # 출발점 처리

    res = []
    while queue:
        node = queue.popleft()

        res.append(node)  # 로직
        for e in graph[node]:
            if not visited[e]:
                visited[e] = 1
                queue.append(e)
    return res


# DFS-1: 재귀했을 때 조건검사
def dfs(node, res=[]):
    if not visited[node]:
        visited[node] = 1
        res.append(node)  # 로직
        for e in graph[node]:
            res = dfs(e, res)
    return res


# DFS-2: (노드에서 방문마킹) 재귀호출 직전에 조건검사
def dfs2(node, res=[]):
    visited[node] = 1
    res.append(node)  # 로직
    for e in graph[node]:
        if not visited[e]:
            res = dfs2(e, res)
    return res


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

graph = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

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


visited = [0] * (N+1)
ans = dfs(V)
print(" ".join(map(str, ans)))

ans = bfs(V)
print(" ".join(map(str, ans)))