DFS와 BFS
위 이미지는 DFS(Depth First Seach)의 구현 동작이며 말그대로 자식노드의 마지막 노드 까지 갔다가 다시 올라와서 옆에 형제 노드들을 같은 방식으로 반복하여 검색하는 깊이 우선 탐색이다.
이때 다시 되돌아오는것을 backtraking이라고 한다.
- 구현하는것은 BFS보다 빠르지만 단순 검색속도는 느리다.
- 인접리스트와 인접행렬 두가지로 stack 과 재귀함수를 구현 할 수 있다.
- 메모리 사용공간이 적다.
- DFS는 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회하므로 시간복잡도는
인접리스트는 O(N+E) , 인접행렬은 O(N^2)이므로 인접리스트방식이 좀 더 효율적이다.
위 이미지는 BFS(Breadth first search)의 구현 동작이며 시작 루트에서 자신의 자식들을 모두 먼저 방문하고 그다음의 자식의 자식노드들을 모두 방문하는 너비 우선 탐색이다.
- 두 노드사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 쓰이는 방법이다
- 인접리스와 인접행렬 두가지로 Queue를 구현하고 선입선출 방식으로 탐색한다.
- 경로가 길어지게 되면 탐색구간이 많아지므로 메모리 사용공간이 많아진다.
- 구현이 복잡하고 재귀함수로 동작하지 않는다.
- 모든 정점을 한 번씩 방문하며, 정점을 방문할 때마다 인접한 간선을 모두 검사하기 때문에 시간복잡도는 DFS와 같다.
Backtracking
백트래킹은 조건에 맞는 모든 경우를 찾고 싶을 때
조건이 맞는 값을 찾을때 까지 단계가 넘어가다가 더이상 넘어갈 길이 없으면 한칸 후퇴하고 다시 반복하는 방법이다.
한 노드의 유망성을 검사하고 유망하지 않을 경우 다시 부모노드로 돌아가서 다른 자식노드를 검색하는 방식이다. 유망성이란
n-Queens 문제를 예시로 들어보자면
퀸이 공격당하지 않는 자리에 다른 퀸들을 놓을 수 있도록 하는 문제인데
이것을 그래프로 나타내면
이런식으로 될텐데 깊이 우선 탐색에서는 (1,1)에 (2,1)(2,2)(2,3)(2,4)를 스택에 넣을테지만
백트래킹에서는 (2,1)(2,2)는 스택에 넣지 않는다. 바로 유망성이 없기 때문이다.
이처럼 백트래킹은 스택에 자식노드를 넣기전에 유망한지 즉, 답이 될 수 있는지 확인한 뒤 스택에 넣는다.
만약에 (2,3)에 큐를 놓을 경우 3행에는 놓을 자리가 없다. 그러므로 자식노드가 하나도 없는것과 마찬가지이므로 유망성이 없다. 그래서 (2,4)가 유망성이 있다고 볼 수 있다.
