[백준-1260] DFS와 BFS - Python

 

 

문제 : [백준-1260] DFS와 BFS - Python

출처 : 백준

 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

---

   사용한 알고리즘  

---

DFS

BFS

---

 

---

   Python Code    

#############################################################################
# 1260
#############################################################################

import sys
import collections

sys.stdin = open("input.txt", "r")

N , M , start_node = list(map(int , input().split(" ")))

#### graph 만들기
graph = collections.defaultdict(list)
for _ in range(M):
    node_start , node_end = list(map(int , input().split(" ")))
    if node_end not in graph[node_start]:
        graph[node_start].append(node_end)
    if node_start not in graph[node_end]:
        graph[node_end].append(node_start)
    graph[node_start].sort()
    graph[node_end].sort()
####

DFS_visited =  []
def DFS(graph , start_node):
    DFS_visited.append(start_node)
    for node in graph[start_node]:
        if node not in DFS_visited:
            DFS(graph,node)

BFS_visited = []
def BFS(start_node):
    Q = collections.deque([])
    Q.append(start_node)
    BFS_visited.append(start_node)
    while Q:
        x = Q.popleft()
        for node in graph[x]:
            if node not in BFS_visited:
                Q.append(node)
                BFS_visited.append(node)



DFS(graph,start_node)
# for i in list(graph.keys()):
#     if i not in DFS_visited:
#         DFS(graph, i)
print(*DFS_visited)

BFS(start_node)
# for i in list(graph.keys()):
#     if i not in BFS_visited:
#         BFS(i)
print(*BFS_visited)