백트래킹(Backtracking)이란? 백준 문제 추천

백트래킹(Backtracking)이란? 문제 추천

조감도

• 참고. 알고리즘 공부 리스트 및 순서
• 백트래킹은 완전 탐색의 카테고리에 있습니다. 백트래킹으로 해결할 수 있는 유명한 N-Queens 문제가있습니다.

백트래킹(Backtracking)이란?

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, that incrementally builds candidates to the solutions, and abandons each partial candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution. (Wikipedia)

• 완전탐색의 아이디어에서 불필요한 분기(Branch) 를 가지치기(Pruning) 하는 것입니다.
• 정답을 도출하기 전 탐색과정 중에 정답이 될 수 없는 조건에 해당된다면 가지치기하여 효율을 높일 수 있습니다.
• 복수의 해를 구할 수 있습니다.
• 적용대상
  • 다른 알고리즘 방법으로 해결하기 힘들어 전수 조사가 필요한 경우
  • 다른 알고리즘 방법으로는 비효율적인 문제(ex. NP)

백트래킹 적용 예제

• 예제: 라이언, 어파치, 무지가 교실 책상에 앉으려고 합니다. 교실 책상은 3개의 책상이 나란히 있으며 어파치는 라이언과 무지 가운데에 앉을 수 없습니다. 자리를 앉을 수 있는 경우의 수를 모두 구하세요.

문제에 해당하는 *상태공간트리(State-Space Tree) 는 다음과 같습니다.

상태공간트리란?

1. 해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리입니다.
2. 트리의 모든 노드들을 방문하면 해를 찾을 수 있습니다.
3. 루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술합니다.

• 상태공간트리를 보았을 때 총 4개의 경우의 수가 있습니다.

백트래킹 알고리즘

ExhaustiveSearch(Node v)
{
[1]        if (Solution exist at v) Write Solution
[2]     else for (each child u of v) ExhaustiveSearch(u)
}

• [1] 줄 : v노드에서 답이 되는 경우 해로 결정 합니다.
• [2] 줄 : v노드의 자식노드가 해가 되는지 계속 탐색 합니다.
• 본 알고리즘은 DFS와 흡사 합니다. 왜 DFS와 흡사할까요? 다시 예제로 돌아가봅시다.

• 해가 나올 때까지 상태공간트리의 맨 아래까지 탐색을 합니다. 그러기에 DFS와 흡사하다고 합니다.

기본을 다질 수 있는 문제 추천

• [백준 1182 부분 수열의 합] 문제 및 해설
• [백준 1759 암호 만들기] 문제 및 해설
• [백준 2661 좋은 수열] 문제 및 해설
• [백준 1405 미친로봇] 문제 및 해설

 

---

참고자료

• [YouTube] 6 Introduction to Backtracking - Brute Force Approach - (by Abdul Bari)
• [YouTube] 6.1 N Queens Problem using Backtracking
• [YouTube] 29.3 백트래킹 (Backtracking Method)
• [알고리즘] 제2-3강 Recursion의 응용: n queens problem

이미지 출처

• 무지, 라이언, 어파치 카카오 이모티콘 (by. Kakao)
• Cancel free icon
• Checked free icon