[알고리즘]#6_백 트래킹

 

[알고리즘]#6_백 트래킹

 

백 트래킹 알고리즘에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 개념
2. 예제

 

#0. 개념

1. 백 트래킹

• 백 트래킹 알고리즘은 문제 해결을 위해 여러 후보 해결책들을 점진적으로 탐색하며, 현재 선택한 경로가 해결책으로 이어질 수 없다고 판단되면, 이전 단계로 돌아가(백 트래킹) 다른 경로에 대한 탐색을 시도하는 방법입니다. 이처럼 백 트래킹 과정을 통해 문제의 모든 후보 해결책들을 효과적으로 탐색할 수 있습니다. 특히, 백 트래킹 알고리즘은 모든 가능한 해결책 후보를 조합적으로 탐색해야 할 때, 최고의 성능(시간, 자원)을 보여줍니다.
• 따라서, 백 트래킹 알고리즘은 (1) 미로 찾기, (2) 스도쿠, (3) 순열, (4) 조합, (5) N-Queens 문제, 그리고 (6) 그래프의 탐색 경로 찾기 문제 등에 활용됩니다.

 

2. 동작 방식

1. 탐색 시작 : 해결책 후보를 구축하기 위해 가능한 후보 경로를 탐색합니다.
2. 조건 만족 여부 확인 : 현재 경로에 대해 문제의 조건과 제약사항을 만족하는지 확인합니다.
3. 조건 여부 만족 : 만약, 문제의 조건과 제약사항을 현재 경로가 만족한다면, 현재 경로의 다음 단계로 다음 후보 해결책들을 탐색합니다.
4. 조건 여부 불 만족 : 만약, 문제의 조건과 제약사항을 현재 경로가 만족하지 않을 경우, 현재 후보를 버리고 같은 단계의 다른 후보로 탐색을 시작합니다.
5. 현재 후보에 대한 탐색 성공 : 현재 후보에 대한 2 ~ 4번 과정을 반복하여 최종 해결책을 찾아냅니다.
6. 현재 후보에 대한 탐색 실패 : 더 이상 가능한 후보가 없다면, 이전 단계로 돌아가 다른 후보를 탐색합니다.
7. 위 과정들을 반복하고, 최종 해결책을 찾아내거나, 해결책이 존재하지 않는다고 판단될 때까지 진행합니다.

 

#1. 예제

1. 순열 문제

[확률과 통계]#1 순열, nPr

[BOJ알고리즘, C++]#15649_N과 M(1), 깊이 우선 탐색

 

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int> ans;
vector<bool> visited;

void dfs(int depth)
{
    if(depth == M)
    {
        for(int i=0 ;i<M; i++)
        {
            cout << ans[i] << ' ';   
        }
        cout << '\n';
        return;
    }
    for(int i=1; i<=N; i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            ans.push_back(i);
            dfs(depth+1);
            visited[i] = false;
            ans.pop_back();
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int N, M;
    cin >> N >> M;
    
    visited.assign(N+1, false);   
    dfs(0);
    
    return 0;
}

 

Details

 

• 1 ~ N개의 숫자 중 M개의 숫자를 중복 없이 뽑아 사전 순으로 나열하는 "순열(nPm)" 문제입니다.
• DFS(깊이 우선 탐색)을 통해 가능한 후보들에 대한 탐색을 수행합니다. 그리고, 문제가 제시한 조건과 제약 사항들을 현재 선택한 경로가 만족하는지 체크합니다. 위 문제의 조건과 제약 사항은 (1) 중복이 없는(방문 여부), 그리고 (2) M개 의 숫자 조합입니다. 현재 경로가 해당 조건과 제약사항을 만족한다면 다음 단계의 가능한 후보들에 대한 탐색을 진행합니다. 반대로, 만족하지 않는다면 현재 후보를 버리고 i+1, 즉 같은 단계의 다음 가능한 후보를 탐색합니다.

 

2. 조합 문제

[확률과 통계]#2 조합, nCr

 

[BOJ알고리즘, C++]#15650_N과 M(2), 백 트래킹, 조합

 

 

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int> ans;

void dfs(int depth, int start)
{
    if(depth == M)
    {
        for(int i=0 ;i<M; i++)
        {
            cout << ans[i] << ' ';   
        }
        cout << '\n';
        return;
    }
    for(int i=start; i<=N; i++)
    {
        ans.push_back(i);
        dfs(depth+1, i+1);
        ans.pop_back();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    cin >> N >> M;   
    dfs(0, 1);
    
    return 0;
}

 

Details

 

• 1 ~ N개의 숫자 중 M개의 숫자를 중복 없이 뽑아 오름차순 나열하는 "조합(nCm)" 문제입니다.
• 순열 문제와 달리 이 문제는 "1 2"와 "2 1"과 동일하게 보는 순서에 상관없는 조합문제입니다. 따라서, 순열 문제와 동일하게 현재 경로가 문제의 조건과 제약사항을 만족할 경우, 현재 경로에서 더 나아가 다음 단계의 가능한 후보들을 탐색합니다. 하지만, 조합 문제는 순열 문제와 달리 현재 경로의 이전 단계에서 탐색한 후보는 현재 단계의 가능한 후보책들의 목록에서 제외됩니다.
• 그 외 동작 방식은 순열문제와 동일합니다.

 

3. N-Queens 문제

 

[BOJ알고리즘, C++]#9663_N-Queen 문제, 백 트래킹

 

#include <iostream>
using namespace std;

constexpr int MAX = 15;

int col[MAX];
int N, result=0;

bool check(int colNum)
{
    for(int i=0; i<colNum; i++)
        if(col[i] == col[colNum] || abs(col[colNum] - col[i]) == colNum - i)
            return false;
    return true;
}

void nqueen(int colNum)
{
    if(colNum == N)
        result++;
    else
    {
        for(int i=0; i<N; i++)
        {
            col[colNum] = i;
            if(check(colNum))
                nqueen(colNum+1);
        }   
    }
}

int main () {
    cin >> N;
    nqueen(0);
    cout << result << endl;
}

 

Details

 

https://upload.wikimedia.org/wikipedia/commons/1/1f/Eight-queens-animation.gif

 

• N-Queen 문제는 대표적인 백 트래킹 알고리즘 문제 중 하나입니다.
• N x N 크기의 체스판에서 퀸들이 서로 공격할 수 없도록 배치하는 방법은 각 행(Column)마다 하나의 퀸만 배치하는 것입니다. 추가적으로, 각 퀸들의 위치는 여타 다른 퀸들의 대각선에 위치해서도 안됩니다. 따라서, N-Queen 문제를 해결하기 위한 백 트래킹 알고리즘은 조건 및 제약사항으로 위 조건들을 추가합니다.
• 위 코드에서 check() 함수는 현재 가능한 후보가 위 조건을 만족하는지 확인하며, 해당 조건을 만족하면 현재 경로의 다음 단계로 넘어가 다음 가능한 후보책들에 대한 탐색을 진행합니다. 반대로, 현재 경로가 문제의 조건을 만족하지 않는다면, 같은 단계의 다음 후보에 대한 탐색을 진행합니다. 

 

4. 정리

[자료구조]#6_그래프

 

• 정리하자면, 백 트래킹 알고리즘은 경로 탐색을 위해 DFS(깊이 우선 탐색)을 활용하며, 이에 조건과 제약사항을 추가해 현재 경로에 대한 탐색을 계속 진행할 것인지 결정합니다. 
• DFS(깊이 우선 탐색)은 재귀 호출 혹은 스택을 활용해 그래프 자료구조의 모든 정점을 탐색하는 알고리즘입니다.