[Algorithm] 18강 : DFS(깊이 우선 탐색) 알고리즘 정의와 예제

 

# DFS 알고리즘이란?

 

DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

DFS는 스택 자료구조(혹은 재귀 함수)를 이용

 

 

#단계

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

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리

 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

 

 # DFS 동작 예시

시작 노드는 1번으로 시작된다. 이다음은 1번과 인접한 노드로 이동한다. 이중 가장 작은 노드인 2로 이동한다.

 

이런 식으로 인접한 노드를 모두 접근한다. 그 다음 접근할 노드가 없다면 스택에서 해당 값을 빼면서 다시 이동한 노드를 찾는다.

 

 

이런식으로 모든 노드에 접근하면 아래와 같이 된다.

 

 

# DFS 소스코드 예제(python)

#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 = [
	[],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

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

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

 

---

www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

이 자료는 동빈 나 님의 이코 테 유튜브 영상을 보고 정리한 자료입니다.