DFS : 깊이 우선 탐색

• 루트노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘

1. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사함
2. 즉 넓게(wide) 탐색하기 전에 깊게(deep) 탐색함
3. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
4. 깊이우선탐색(DFS)이 너비우선탐색(BFS)보다 좀 더 간단함
5. 검색 속도 자체는 너비우선탐색(BFS)에 비해서 느림

과정

시간 복잡도

DFS는 그래프 (정점의 수 N, 간선의 수 E)의 모든 간선을 조회함
인접 리스트로 표현된 그래프 : O(N+E)
인접 행렬로 표현된 그래프 : O(N^2)

특징

자기 자신을 호출하는 순환 알고리즘 형태를 지님
이 알고리즘을 구현할 때 가장 큰 차이점은
그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것
-> 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있음

구현

stack과 recursive function을 이용하여 구현한다.

- 동작 과정
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

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

→ DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어 0(N)의 시간이 소요된다.
→ 재귀함수를 이용했을 때 매우 간결하게 구현할 수 있다.

#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차원 리스트)
visited=[False]*9

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

BFS VS DFS

방문 순서에서 큰 차이가 있다.

BFS
상하 좌우로 퍼져나가고 거리순으로 방문함

DFS

거리를 계산할 때는 DFS를 사용할 수 없다.
다차원 배열에서 순회하는 문제는 BFS만 쓴다.
DFS는 나중에 그래프와 트리라는 자료구조를 배울때 DFS가 필요하게 된다.

출처
바킹독, 동빈나 블로그