자료구조

DFS/BFS 및 백트래킹 알고리즘

Grey Kang 2021. 3. 23. 17:57
반응형

DFS

정의

  • DFS는 깊이 우선 탐색의 약자로서 그래프 순회 방법이다
  • DFS는 한 지점(vertex)에서 간선을 타고 아래로 계속 내려가면서 끝에 도달한다. 도착 지점이 아닌 경우, 다시 돌아와 다른 지점에서 간선을 타고 탐색을 계속 하다가 도착 지점에 도달하면 종료한다. 그러다보니 DFS는 방향이 있는 그래프에서 구현한다.

구현

  • DFS는 주로 재귀 함수의 연속 호출로 구현을 하거나 스택으로 구현한다. 주로 재귀로 구현하는 것 같은데 백트래킹 알고리즘이 DFS를 대표적으로 구현하는 예이다.
  • 재귀로 구현할 때와, 스택으로 구현할 때의 탐색 순서가 다를 수 있다.
  •  DFS는 방향이 있는 그래프에서 구현한다.

 

[재귀]
1. 재귀로는 일단 지점 1부터 지점1이 연결되는 끝까지 파고 들어간 다음,

  1. 다시 하나 올라와서 올라온 지점의 다른 경로로부터 탐색을 다시 시작한다.

[스택]
1. 스택은 시작 지점을 먼저 삽입하고, 시작지점과 연결된 지점들을 모두 스택에 넣는다.

  1. 그 후 가장 마지막에 삽입된 지점부터 꺼내서(pop),
  2. 그 지점의 하위 지점을 탐색하고 스택에 넣는다.
  3. 그리고 마지막에 삽입 된 지점을 꺼내기 때문에, 2번에 삽입한 지점이 끝까지 탐색하기 전까지는 1번에서 넣었던 나머지 지점을 탐색할 수 없다.

즉, 가장 마지막에 넣은 지점부터 계속 탐색 한다고 보면 된다.

 

백트래킹

  • 백트래킹은 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기해 정답을 찾아가는 범용적인 알고리즘으로 제약 충족 문제를 풀 때 주로 쓰인다.
  • 탐색을 예로 들면 이 길이 아닌 것 같으면 왔던 길로 되돌아와 다른 선택지로 간다고 생각하면 될 것 같다.
  • 백트래킹은 재귀로 보통 구현하는데, 재귀 함수가 호출되고 조건에 맞지 않으면 종료되고 그전에 호출된 재귀로 돌아오므로, 백트래킹에서 말하는 '가능성이 없으면 후보를 포기해 정답을 찾아가는(다시 왔던 길로 돌아가는) 느낌이라고 할 수 있겠다.
  • 안 되는 조건은 없애면서 탐색하기 때문에 시간복잡도가 선형적으로 증가할 법한 문제에서 백트래킹을 적용하면 시간복잡도를 줄일 수 있다.
# 재귀로 구현한 코드
def recursive_dfs(vertex, visited=[]):
	visited.append(vertex)
	for item in graph[vertex]:
		if not item in visited:
			visited = recursive__dfs(item, visited)
	return visited

# 스택으로 구현한 코드
def stack_dfs(start_vertex):
	visited = []
	stack = [start_vertex]
	while stack:
		vertex = stack.pop()
		if vertex not in visited:
				visited.append(vertex)
				for item in graph[vertex]:
					stack.append(item)
	return visited

BFS

  • BFS 또한 탐색방법으로서 너비 우선 탐색의 약자이다.
  • DFS와 다르게 횡으로 움직이면서 지점을 탐색하는 것이다. 시작 지점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 지점은 나중에 방문하는 개념이다. 그러니 넓게 탐색한다고 할 수 있다.
  • 주로 최단 경로를 찾고 싶을 때 BFS를 사용한다. 대표적으로 다익스트라 알고리즘에서 사용된다.

 

코드

def iterative_bfs(start_vertex):
	visited = [start_vertex]
	queue = [start_vertex]
	while queue:
		vertex = queue.pop(0)
		for item in graph[vertex]:
			if item no in visited:
				visited.append(item)
				queue.append(item)
	return visited
반응형