[알고리즘]Backtracking 알고리즘

1. Backtracking 이란?

주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
즉, 백트래킹은 조건이 만족할 때의 모든 조합의 수를 살펴보는 방법입니다.

• BackTraking에 대한 설명은 예제를 통해 설명하겠습니다.

2. 예제

1) N과 M(1)

문제

입력 : N, M
출력 : 1~N까지 자연수 중에서 중복 없이 M개를 고른 순열들을 출력

생각해야 하는 조건

1. 1~N개의 원소가 반복되면 안 된다.
2. 길이가 M일 경우 해당 순열을 출력한다.

BackTracking 코드

void BackTracking(vector<int> v, int arr[]) {
    if (v.size() == m) { //길이가 M일 경우
        for (int i = 0; i < m; i++)
        {
            cout << v[i] <<" ";
        }
        cout << "\n";
        return ;
    }
    for (int i = 1; i <= n; i++)
    {
        if (arr[i] != 1) { //원소 사용 여부 확인
            v.push_back(i);
            arr[i] = 1;//사용했음을 체크
            repeat(v, arr);
            arr[i] = 0;//사용했음 해제
            v.pop_back();
        }
    }

}

전체 코드

#include <iostream>
#include <vector>

using namespace std;
int n, m;

void repeat(vector<int> v, int arr[]) {
    if (v.size() == m) { //길이가 M일 경우
        for (int i = 0; i < m; i++)
        {
            cout << v[i] <<" ";
        }
        cout << "\n";
        return ;
    }
    for (int i = 1; i <= n; i++)
    {
        if (arr[i] != 1) { //원소 사용 여부 확인
            v.push_back(i);
            arr[i] = 1;//사용했음을 체크
            repeat(v, arr);
            arr[i] = 0;//사용했음 해제
            v.pop_back();
        }
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    vector<int> answer;
    int *arr = new int[n+1];
    arr[0] = 1;//사용하지 않을 것이기에 미리 체크해놓음.
    repeat(answer,arr);


    return 0;
}

---

2) N-Queen

문제

N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제

입력 : N
출력 : 모든 경우의 수

생각해야 하는 조건

1. 퀸이 공격할 수 있는 방향 체크
2. 퀸이 N개일 때 count++

BackTracking코드

bool used1[40],used2[40],used3[40];
//used1 : 같은 행에서 열 중복 확인
//used2 :(왼->오 기준)내려가는 대각선 확인
//used3 : (왼->오 기준)올라가는 대각선 확인

void BackTracking(int row) {
    if (row == n) {
        answer++;
        return;
    }
    for (int col = 0; col < n; col++)
    {
        if (used1[col] || used2[col + row] || used3[row - col + n - 1])
            continue;
        used1[col] = true;
        used2[col + row] = true;
        used3[row - col + n - 1] = true;
        BackTracking(row + 1);
        used1[col] = false;
        used2[row+col] = false;
        used3[row - col + n - 1] = false;
    }
}

자세한 코드에 대한 설명은 여기서

 

전체 코드

#include <iostream>

using namespace std;

int n, answer = 0;

bool used1[40],used2[40],used3[40];
//used1 : 같은 행에서 열 중복 확인
//used2 :(왼->오 기준)내려가는 대각선 확인
//used3 : (왼->오 기준)올라가는 대각선 확인

void BackTracking(int row) {
    if (row == n) {
        answer++;
        return;
    }
    for (int col = 0; col < n; col++)
    {
        if (used1[col] || used2[col + row] || used3[row - col + n - 1])
            continue;
        used1[col] = true;
        used2[col + row] = true;
        used3[row - col + n - 1] = true;
        BackTracking(row + 1);
        used1[col] = false;
        used2[row+col] = false;
        used3[row - col + n - 1] = false;
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    BackTracking(0);
    cout << answer;

    return 0;
}

---

<참조 링크>

https://blog.encrypted.gg/732? category=773649
https://jeongdowon.medium.com/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-backtracking-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-13492b18bfa1