[Python]DFS와BFS 백준 1260

 문제

 https://www.acmicpc.net/problem/1260

DFS와 BFS는 각각 깊이우선탐색 너비우선탐색이다.

방문할수 있는 모든 정점을 방문하는 방법으로 그 순서에 따라 DFS와 BFS로 나뉜다.

DFS는 깊이 우선탐색은 Binary tree를 탐색했던 방식인 

postorder(전위 순회(부모노드->왼쪽자식->오른쪽자식)) 

inorder(중위순회(왼쪽자식->부모노드->오른쪽자식))  

preorder(후위순회(왼쪽자식->오른쪽자식->부모노드)) 방식이 이에 해당된다.

이 문제에서는 전위 순회를 이용하였다.

DFS는 스택에 방문한 정점들을 스택에 저장하였다가 다시 꺼내면서 해당노드의 

자식노드들을 다시 스택에 쌓는방식이고 BFS는 큐를 이용하여 자식노드들을 모두 

넣고 꺼내면서 해당노드의 자식노드들을 큐에 쌓아 큐가 모두 소진될때까지 반복하여 

구현한다.

DFS는 재귀를 통해 구현하면 더욱 깔끔하게 구현할수 있다.

코드를 통해 살펴보자.

import sys
 
 
#current_node : 시작 정점, row : 인접 행렬, foot_print : 발자취 리스트
def dfs(current_node,row,foot_prints):#깊이우선탐색
    foot_prints+=[current_node]#먼저 리스트에 쌓아줌
    for search_node in range(len(row[current_node])):#연결된 노드 탐색
        if row[current_node][search_node] and search_node not in foot_prints:#연결되어 있고 한번도 방문하지 않았다면
            foot_prints=dfs(search_node,row,foot_prints)#해당노드에서 다시 재귀로 실행
    return foot_prints
 
 
#
def bfs(start):#너비우선탐색
    #큐를 이용해 구현하면 편하다
    queue=[start]#시작점을 큐에 넣어준다
    foot_prints=[start]#출력할 노드를 담아준다.
    while queue:#queue가 빌때까지 실행한다.
        current_node=queue.pop(0)#먼저 큐에서 하나의 노드를 꺼내고
        for search_node in range(len(matrix[current_node])):#해당 노드와 연결된 모든 노드를검색해
            if matrix[current_node][search_node] and search_node not in foot_prints:#연결되어 있으며 방문하지 않았다면
                foot_prints += [search_node]#출력노드에 추가해주고
                queue += [search_node]#모두큐에 담아준다.
    return foot_prints
 
 
#정점 개수,간선 개수, 시작 정점
N,M,V=map(int,sys.stdin.readline().split())
matrix=[[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
    start,end=map(int,sys.stdin.readline().split())
    matrix[start][end]=1#연결된 간선을 1로 표시해줌
    matrix[end][start]=1#양방향 연결이므로 반대로 가는 방향도 1로 표시해줌
 
 
# # *붙인 이유는 리스트 형태를 풀어주기 위함
print(*dfs(V,matrix,[]))
print(*bfs(V))
 

BFS를 구현할때 deque모델을 이용하면 실행시간을 많이 줄일 수 있을거같다.