백준(BeakJoon)_1260_DFS와BFS

# DFS를 재귀로 풀었을 때 

from collections import deque

def DFS(graph, visited, start_node): 

    visited[start_node] = True
    print(start_node, end=" ")   
    for i in graph[start_node]:
        if not visited[i]:
            DFS(graph,visited,i)


def BFS(graph, visited, start_node):
    queue = deque()
    queue.append(start_node)  # 노드를 qeue에 넣어준다 
    visited[start_node] = True  

    while queue:
        current_node = queue.popleft()
        print(current_node, end=" ")

        for n in graph[current_node]:
            if not visited[n]:
                queue.append(n)
                visited[n] = True
      


if __name__ == "__main__":
    node, line, start_node = map(int, input().split())
    graphs = [[] for _ in range(node+1)] 
    for _ in range(line):             
        n1, n2 = map(int, input().split())
        graphs[n1].append(n2)
        graphs[n2].append(n1)
        
    # 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문이라는 지문이 있어서 각각의 노드들을 오름차순으로 정렬
    for graph in graphs:  # 오름차순 정렬 
        graph.sort()  


dfs_visited = [False] * (node+1)     
bfs_visited = [False] * (node+1)     

DFS(graphs, dfs_visited, start_node)
print()
BFS(graphs, bfs_visited, start_node)

 

 

# DFS를 스택으로 풀었을 때 

from collections import deque 

def DFS(graph, visited, start_node):
    stack = deque()
    stack.append(start_node)

    while stack:
        s = stack[-1]
        stack.pop()

        if not visited[s]:
            print(s, end=" ")
            visited[s] = True 

        for node in graph[s]:
            if not visited[node]:
                stack.append(node)   
def BFS(graph, visited, start_node):
    queue = deque()
    queue.append(start_node)  # 노드를 qeue에 넣어준다 
    visited[start_node] = True  

    while queue:
        current_node = queue.popleft()
        print(current_node, end=" ")

        for n in graph[current_node]:
            if not visited[n]:
                queue.append(n)
                visited[n] = True
      
if __name__ == "__main__":
    node, line, start_node = map(int, input().split())
    graphs = [[] for _ in range(node+1)] 
    for _ in range(line):             
        n1, n2 = map(int, input().split())
        graphs[n1].append(n2)
        graphs[n2].append(n1)
        

   
dfs_graph = [sorted(graph, reverse=True)  for graph in graphs]
bfs_graph = [sorted(graph) for graph in graphs]

dfs_visited = [False] * (node+1) 
bfs_visited = [False] * (node+1)     


DFS(dfs_graph, dfs_visited, start_node)
print()
BFS(bfs_graph, bfs_visited, start_node)