[알고리즘] 백트래킹(Backtracking)과 DFS, BFS
백트래킹(Backtracking)이란?
백트래킹(Backtracking)이란 퇴각검색이라고도 불리며 한정 조건을 가진 문제를 푸는 전략입니다. 이름의 의미 그대로 원하는 해를 찾다가 한정 조건에 도달하면 뒤로 돌아가면서 다시 해를 찾는 탐색 방식입니다.
원하는 해를 찾지 못했을 때 탐색을 처음부터 다시 시작하는 것이 아니라 이전 노드로 돌아가기 때문에 반복 횟수를 줄일 수 있는 장점이 있습니다. 추가적으로 현재 경우가 얼마나 유망한지 일찍 판단할 수 있다면 탐색의 속도를 상향시킬 수 있습니다.
💡 백트래킹은 트리 구조를 기반으로 구현하는 경우가 많기 때문에 한정 조건에 도달하여 뒤로 돌아가 현재 경우 수를 제거하는 것을 가지치기를 한다고 이야기합니다.
백트래킹은 일반적으로 DFS(Depth First Search, 깊이 우선 탐색) BFS(Breath First Search, 너비 우선 탐색)로 구현 가능합니다.
💡 백트래킹과 DFS, BFS 백트래킹과 DFS, BFS는 교집합 관계라고 볼 수 있습니다. 기본적으로 DFS와 BFS는 완전 탐색을 기반으로 만들어졌지만 백트래킹은 완전 탐색을 해야만하는 것은 아닙니다. 그렇기 때문에 백트래킹을 DFS와 BFS로 응용하여 구현할 수 있을 뿐 DFS와 BFS가 백트래킹에 종속되는 개념은 아닙니다.
DFS(깊이 우선 탐색)이란?
출처 위키미디어
DFS(Depth First Search)는 깊이를 우선적으로 탐색하는 방식으로 하나의 분기에 대해서 완전하게 탐색하는 방식입니다. 루트 노드 혹은 부모 노트에서 시작하여 해당 분기를 끝까지 탐색하고 해당 분기의 탐색이 끝났다면 다시 다른 분기로 이동 가능한 상위 노드로 돌아와 다음 분기를 탐색하는 방식입니다.
하나의 분기에 대해서 완전히 탐색을 하기 때문에 특정 구간 혹은 경로에 대해 탐색해야 할 경우 자주 사용합니다.
LIFO(후입선출)방식인 스택과 재귀함수로 많이 구현됩니다.
동작과정
DFS의 동작 과정을 이해하려면 방문 처리에 대해서 알아야 합니다. 방문 처리는 분기를 탐색하며 탐색한 노드들에 대해서 방문했다는 표시를 하는 것입니다. 이러한 방문 처리를 하는 이유는 하나의 분기를 완전하게 탐색했을 때 다음분기 탐색을 위해 상위 노드로 이동할텐데 이 때 방문했는지 확인할 수 없다면 무한 루프에 빠질 것입니다. 그렇기 때문에 탐색한 노드에 대해서는 반드시 방문 처리를 해줘야합니다.
다시 돌아와 동작과정을 보자면 다음과 같습니다.
스택에 시작 노드를 삽입 후 방문 처리
인접한 노드중 방문 처리가 되어 있지 않은 노드가 있다면 스택에 삽입 후 방문 처리, 인접 노드가 없다면 모두 pop
2번의 과정을 할 수 없을 때까지 반복
예시
추가예정!
BFS(너비 우선 탐색)이란?
출처 위키미디어
BFS(Breadth First Search)는 너비를 우선적으로 탐색하는 방식으로 가까운 노드를 먼저 탐색하는 방식입니다. 루트 노드에서 시작하여 가장 가까운 노드부터 방문하여 점차 모든 노드를 방문하며 탐색하는 방식입니다.
가까운 노드를 우선적으로 탐색하기 때문에 최단경로를 탐색할 때 자주 사용합니다.
FIFO(선입선출)방식인 큐로 많이 구현됩니다.
동작과정
큐에 시작 노드를 삽입 후 방문 처리
큐에서 노드를 꺼내 방문하지 않은 모든 인접 노드를 큐에 삽입 후 방문 처리
2번의 과정을 할 수 없을 때까지 반복
예시
추가예정!
마무리
백트래킹, DFS, BFS에 대해서 알아봤습니다! 비슷한듯 다른 개념들을 한번에 학습했는데 도움이 되었으면 좋겠습니다! 방문해주셔서 감사합니다!
Reference
https://ko.wikipedia.org/wiki/퇴각검색