[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(5) - DFS

#책 페이지 

p.137

 

#탐색 알고리즘 DFS에서 사용하는 자료구조

스택 자료구조

 

#DFS는 어떻게 동작할까?

👉DFS는 '깊이 우선 탐색 알고리즘' 이다. 이 알고리즘은 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.

 

👉DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다. 

①탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.

②스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 

①,②번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

 

⭐방문처리?

스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다. 

 

⭐DFS의 기능을 생각하면 순서와 상관없이 처리해도 되지만, 코딩테스트에서는 번호가 낮은 순서부터 처리하도록 명시하는 경우가 종종 있다. 따라서 관행적으로 번호가 낮은 순서부터 처리하도록 구현하는 편이다. 

 

┌동작과정을 아래와 같이 그림으로 표현해보았다.

 

▲결과적으로 노드의 탐색 순서(=스택에 들어간 순서) 는 다음과 같다. 1->2->7->6->8->3->4->5

 

#DFS의 시간복잡도

DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다는 특징이 있다. 

 

#스택을 이용하는 알고리즘의 구현?

또한, DFS는 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다. 

[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(3)_DFS,BFS에 필요한 자료구조 - 재귀 함수 (tistory.com)

[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(3)_DFS,BFS에 필요한 자료구조 - 재귀 함수

└위 포스팅에서도 스택을 사용하는 알고리즘은 재귀 함수를 이용해서 구현할 수 있다고 나와있다. 

 

#재귀 함수를 이용한 DFS 구현 예제

#DFS 메소드 정의
def dfs(graph, v, visited):
    #현재 노드를 방문 처리한다.
    #처음에 v=1
    visited[v] = True
    print(v, end=' ')

    #현재 노드와 연결된 다른 노드를 재귀적으로 방문한다.
    for i in graph[v]: #i는 1부터시작 i=graph[1]이면 i=2,3,8.. i=graph[2]이면 i=1,7....
        if not visited[i]: #visited[i]가 true가 아니라면 즉,false라면,
            #방문하지 않았을 경우에만 dfs()를 호출, 방문했을 경우에는 노드가 연결된 정보 다음정보로
            dfs(graph, i, visited)

#각 노드가 연결된 정보를 리스트 자료형으로 표현한다(2차원)
graph=[
    [], #노드는 보통 1번부터 시작하니 비워두자.
    [2,3,8], #1번 노드
    [1,7], #2번 노드
    [1,4,5], #3번 노드
    [3,5], #4번 노드
    [3,4], #5번 노드
    [7], #6번 노드
    [2,6,8], #7번 노드
    [1,7] #8번 노드
]

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited=[False]*9 #visited=[False,False,False......]

#정의된 DFS함수를 호출
dfs(graph, 1, visited)

'''
결과
1 2 7 6 8 3 4 5 
'''