백준_실버2_1269번(DFS와 BFS)

이번 문제는 BFS와 DFS구현에 관한 문제이다. 이번 문제를 통해 BFS와 DFS를 구현하는 방식에 대해 알 수 있었다. BFS를 구할때 근접한 노드부터 진행해야하기 때문에, 타겟 노드가 A이고 근접한 노드들이 B일 때, A를 visited에 추가하고 B를 queue에 추가하되 다음 타겟 노드는 근접한 것들 중 가장 왼쪽에 있는 것부터 오른쪽 순서로 뽑아야 함으로 leftpop을 반복적으로 사용하여 다음 타겟노드들을 선택한다.
마찬가지로 DFS를 진행할 때는 한 노드부터 시작해서 가장 깊은 노드로 순서가 진행되어야 하기 때문에, 타겟 노드가 A이고 근접한 노드들이 B일 때, A를 visited에 추가하고 B들 중 끝에 있는 것을 선택하고 그 노드의 자식 노드를 추가하는 방향으로 진행된다.
쉽게 코드에 대해 얘기하자면, pop함수를 사용하여 F노드를 꺼냈다면 F노드들의 자식 노드들을 다음 순서에 추가하되 pop함수를 사용함으로 역순으로 넣어야 옆 노드로 움직이는게 아닌 깊숙히 내려가는 방향으로 진행된다.
그리고 이 문제와 같은 경우에는 주어진 간선이 시작노드를 지나가지 않을 경우가 있기 때문에, 간선을 토대로 그래프를 그리면 에러가 난다. 이를 해결하기 위해서, n개의 노드가 주어질 때, graph dictionary에 노드 전체를 넣었다.

from collections import deque

n,m,v = map(int,input().split(" "))
graph = dict();
for i in range(1, n+1):
    graph[i] = []
for i in range(m):
  start_node,end_node = map(int,input().split())
  graph[start_node].append(end_node)
  graph[end_node].append(start_node)
    
for key,value in graph.items():
  value.sort()


from collections import deque
def bfs(graph,start,n):
    need_visited, visited = deque([start]),deque()
    while need_visited:
        node = need_visited.popleft()
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])

    return visited

from collections import deque
def dfs(graph,start,n):
    need_visited, visited = deque([start]),deque()
    while need_visited:
        node = need_visited.pop()
        if node not in visited:
            visited.append(node)
            need_visited.extend(reversed(graph[node]))
    return visited
    
print(*dfs(graph,v,n))
print(*bfs(graph,v,n))