[파이썬] BFS,DFS, Backtracking(백트래킹)

(자세한 개념 설명보다는 구현 위주의 글입니다.)

DFS,BFS 개념 습득은 아래의 영상을 참고하시길 추천드립니다.

https://www.youtube.com/watch?v=_hxFgg7TLZQ

DFS

• DFS는 깊이 우선 탐색의 약자로서 그래프 순회 방법이다. 그래프라는 개념은 수학자 오일러가 창안했는데 이 글에서 다루진 않는다. 따로 찾아보길 권한다. 그래프 용어에 대한 이해가 없으면 DFS 같은 알고리즘 구현에 어려움을 겪을 수 있기 때문이다.
• DFS는 한 지점(vertex)에서 간선을 타고 아래로 계속 내려가면서 끝에 도달한다. 도착 지점이 아닌 경우, 다시 돌아와 다른 지점에서 간선을 타고 탐색을 계속 하다가 도착 지점에 도달하면 종료한다. 그러다보니 DFS는 방향이 있는 그래프에서 구현한다.

구현

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

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

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

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

2. 그 후 가장 마지막에 삽입된 지점부터 꺼내서(pop),

3. 그 지점의 하위 지점을 탐색하고 스택에 넣는다.

4. 그리고 마지막에 삽입 된 지점을 꺼내기 때문에, 2번에 삽입한 지점이 끝까지 탐색하기 전까지는 1번에서 넣었던 나머지 지점을 탐색할 수 없다.

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

여기서 백트래킹을 잠깐 알고가자.

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

백트래킹을 잘 설명한 글

https://blog.encrypted.gg/732

코드

# 인접간선 설명
graph = {
	1: [2,3,4],
	2:[5],
	3:[5],
	4:[],
	5:[6,7],
	6:[],
	7:[3],
}

# 재귀로 구현한 코드
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를 사용한다. 대표적으로 다익스트라 알고리즘에서 사용된다.

구현

• BFS는 큐를 이용해 구현한다. 큐는 먼저 들어오는 순서대로 뽑아낼 수 있기 때문에,

1. 지점들(vertex)을 순서대로 큐에 넣고 하나 뽑고(pop)

   2. 그 뽑은 지점의 하위 경로를 다시 큐에 넣고

   3. 그 다음 지점을 큐에서 뽑고

   4. 그 지점의 하위 경로를 다시 큐에 넣고.. 하는 식으로 진행된다.

이렇게 구현하면 먼저 넣은 지점들부터 탐색하고 그 후 그 지점들의 하위 지점들을 탐색하는 식으로 진행 된다.

코드

여기서는 리스트를 썼지만 좀 더 효율적으로 사용하려면 deque 같은 자료형을 써도 좋을 것 같다.

# graph는 위의 리스트 사용
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

참고로 BFS는 재귀로 동작하지 않는다.

BFS 참고 : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html