[Algorithm] 백트랙킹 / DFS 차이 - 애매모호한 개념 다잡기

 

일반적으로 코딩테스트 문제를 풀다보면 DFS 와 백트레킹의 단어를 혼용해 가며 문제를 푸는 모습을 스스로 발견할 수 있다. DFS도 개념적으로 알고, 백트래킹도 느낌적으로 알고 있는데, 이 둘의 차이가 조금 있다는 사실을 깨달았다. 그리고 우리가 많이 혼동해 가며 쓰는 개념들을 다시 한번 다잡아 보려고 한다.

 

 

🎯DFS & Backtracking

 

먼저 우리가 알고 있는 DFS 와 백트랙킹 개념 말고 실제 오피셜로 정해진 개념이다.

1. 깊이 우선 탐색 (DFS):
   • DFS는 그래프나 트리와 같은 자료 구조를 탐색하는 알고리즘입니다.
   • 시작 노드에서 시작하여 다음 분기로 넘어가기 전에 현재 분기를 완전히 탐색합니다.
   • DFS는 일반적으로 그래프에서 연결된 모든 노드를 방문하는 목적으로 사용됩니다.
   • 일반적으로 스택이나 재귀 함수를 사용하여 구현됩니다.
2. 백트래킹 (Backtracking):
   • 백트래킹은 문제를 해결하기 위해 가능한 모든 후보 해결책을 조사하면서, 어떤 후보가 현재의 문제의 해가 될 가능성이 없다고 판단되면 해당 후보를 버립니다.
   • 백트래킹은 주로 조합, 순열, 부분 집합, 스도쿠, N-퀸 문제와 같이 결정 문제(Decision Problem)나 최적화 문제(Optimization Problem)에서 사용됩니다.
   • 백트래킹은 DFS를 활용하여 구현될 수 있습니다.

요약하면, 백트래킹은 문제의 모든 가능한 후보를 조사하면서 최적해나 문제의 답을 찾는 것을 목표로 하며, DFS는 그래프나 트리와 같은 자료 구조에서 모든 노드를 방문하는 데 사용됩니다. DFS는 백트래킹의 일부 구현 방법 중 하나일 수 있지만, 백트래킹은 보다 일반적으로 최적화 문제를 해결하기 위한 전략을 의미합니다.

 

위 설명을 보면 다음 그림과 같이 그릴 수 있다.

코딩 테스트는 낮은 시간 복잡도 그리고 낮은 공간 복잡도 그리고 높은 효율성을 가지는 정답을 찾아서 문제를 해결해야 한다. 따라서 DFS 로 문제를 풀때 해당분기가 정답 후보지에서 탈락 하면 그 분기의 자식 노드들은 확인할 필요가 없기 때문에 Cut - edge (컷엣지)라는 걸 통해 가지치기를 하고 다음 분기를 확인하는 로직을 많이 쓴다. 

하지만, DFS 는 그래프의 연결된 모든 노드들을 방문하여 정답을 찾는 완전 탐색에 가깝고, DFS + Cut - edge를 쓰는 방식이 바로 백트래킹이었던 것이다.

 

 

아니면 다음과 같을 수도 있겠다.

 

 

 

🅱️🔙 백트래킹 - Backtracking

 

그러면 백트래킹(Backtracking)은 '해가 아니라면 다시 돌아온다 또는 버린다'고 언급했는데, 이 부분을 가지치기라고 부른다. 즉 불필요한 경로는 굳이 끝까지 탐색하지 않겠다는 것이다. 직관적으로 봐도 백트래킹의 효율성은 얼마나 가지치기를 적절히 해내느냐의 문제로 볼 수도 있을 것이다.

그럼 백트랙킹의 용어 또한 한 번 보고 가려고 한다.

• 유망함(promising): 진행중인 경로가 해답을 찾을 가능성이 있음
• 유망하지 않음(nopromising): 진행중인 경로가 해답을 찾을 가능성이 없음
• 가지치기(pruning): 유망하지 않은 하위 트리를 잘라냄

 

💡내가 혼동하며 쓰던 Cut - edge 라는 것은 가지치기로 원래 개념대로라면 pruning 이었다.

대부분의 문제 풀이를 백트레킹으로 풀고 있던 것이다. 그러나 DFS를 써서 유망하지 않은 가지를 자르는 로직 만 조금 추가하면 되니 많은 문제들이 그냥 DFS 문제로 주제를 정해 둔 것 같다.

 

DFS를 사용한 완전 탐색을 사용한 풀이와 백트랙킹을 사용한 최적의 답을 구하는 대표적인 코테 문제를 몇가지 소개하겠다.

 

 

📜예시문제

 

DFS

프로그래머스 - 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

프로그래머스 - 무인도 여행

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

 

백트랙킹 ( Backtracking )

 

백준 - N과 M

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

백준 - N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

 

참고

https://kwanik.tistory.com/34