알고리즘 with 파이썬 (6) - DFS 깊이 우선 탐색 개념

DFS ( Depth First Search ) : 최대한 멀리있는 노드를 우선으로 탐색하는 방식

특정상황에서 최대한 깊숙이 들어가서 녿를 방문한 후 , 다시 돌아가 다른 경로를 탐색한다.

이 때 스택 자료구조를 이용한다

 

1) 탐색 시작 노드를 스택에 삽입 한 후 방문처리

2) 스택 최상단에 방문하지 않은 인접 노드가 있다면 그 인접노드를 스택에 넣고 방문처리 한다. 또 그 인접노드의 인접노드중 방문하지 않은 게 있다면 스택에 넣고 방문처리 ... (이때 재귀함수가 쓰인다)

3) 방문하지 않은 인접노드가 더 이상 없으면 수행을 멈춘다.

 

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬 

아래는 위 그래프를 DFS 방식으로 탐색하는 코드이다

#DFS 예제

#DFS 메소드 정의
def dfs(graph, v, visited):
    # 현재노드를 방문처리
    visited[v] =True
    print(v,end=' ')
    #현재노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i , visited)

#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph =[
    [],         #0번노드는 없으니깐~!
    [2,3,8],    #1번노드
    [1,7],      #2번노드
    [1,4,5],    #3번노드 연결된 값들
    [3,5],		#4번 ..
    [3,4],		#5번..
    [7],
    [2,6,8],
    [1,7]
]

#각 노드가 방문된 정보를 담을 리스트 자료형(1차원 리스트)
visited = [False]*9

dfs(graph,1,visited)

결과

 

1 2 7 6 8 3 4 5 

 

* 처음에 보고 잘 이해가지 않았는데 스택 구조를 그리면서 해보니 이해가 잘 간다. 생각해보니 정처기에서 이미 한번 처리순서 문제로 경험했던 주제.