[알고개념] 9. Backtracking

1. 백트래킹의 개념

백트래킹은 완전 탐색의 한 종류로, 탐색을 하다가 중간에 답이 나올 수 없는 상황이 생기면 다시 이전 상태로 되돌려서 다른 답을 탐색하는 기법을 의미한다. 백트래킹 문제의 종류에는 아래 3가지가 존재한다.

1. Decision Problem – In this, we search for a feasible solution.
2. Optimization Problem – In this, we search for the best solution.
3. Enumeration Problem – In this, we find all feasible solutions.

백트래킹이 일반적인 재귀와 다른 점은 재귀는 "Base Case"에 도달할 때까지 호출을 반복하지만, 백트래킹은 가장 Best Solution을 찾기 위해 모든 가능성을 탐색한다.

 

2. N-Queen 문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. - https://www.acmicpc.net/problem/9663 

#include <bits/stdc++.h>

using namespace std;

int n;
bool queens[15][15];
int cnt = 0;

// 내가 있는 좌표를 기준으로 퀸이 있는지 확인
bool isSafe(int r, int c) {
    int i, j;
    for (i = 0; i < r; i++) {
        if (queens[i][c]) return false; 
        if (i - r + c >= 0 && i - r + c < n && queens[i][i - r + c]) return false;
        if (r + c - i >= 0 && r + c - i < n && queens[i][r + c - i]) return false;
    }
    return true;
}

void backtracking(int level) {    
    for (int i = 0; i < n; i++) {
        if (isSafe(level, i)) {
            if (level >= n-1) { cnt++; continue; }
            queens[level][i] = true;
            backtracking(level + 1);
            queens[level][i] = false;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    memset(queens, false, sizeof(queens));

    cin >> n;
    backtracking(0);
    cout << cnt;

    return 0;
}

레벨 0부터 시작하여 퀸이 하나 놓일 때마다 레벨을 올리고 queens[level][i]를 true로 바꾸고 다음 행동을 탐색한다. isSafe 한 경우에만 다음 행동을 지속하고, 그렇지 않으면 queens[level][i]를 다시 false로 바꾸고 이전 행동으로 돌아온다. 이런 과정이 백트래킹을 구현한 것이다.

 

3. 스도쿠

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오. - https://www.acmicpc.net/problem/2580

#include <bits/stdc++.h>

using namespace std;
void sudoku(int);

typedef pair<int, int> pii; // pair 타입 앨리어스

int board[10][10];
vector<pii> zeros;
bool visited[3][3][10]; // 3*3 방문 배열
bool isFinished = false;

// level: 빈칸 채운 개수 (dfs)
void sudoku(int level) {
    // level이 zeros 개수만큼 도달 시 끝
    if (level == zeros.size()) { isFinished = true; return; }

    // row, col: 빈칸의 좌표
    int row = zeros[level].first;
    int col = zeros[level].second;

    // 현재 빈칸으로부터 가로, 세로, 3*3 빈칸 중 없는 숫자 찾기
    bool numbers[10] = { 0, };
    
    for (int i = 1; i <= 9; i++) {
        if (board[row][i] != 0) numbers[board[row][i]] = true; // 가로
        if (board[i][col] != 0) numbers[board[i][col]] = true; // 세로
        if (visited[(row-1)/3][(col-1)/3][i]) numbers[i] = true; // 3*3
    }

    // 없는 숫자들을 빈칸에 대입해보고, 재귀호출. 그리고 백트래킹
    for (int i = 1; i <= 9; i++) {
        if (!numbers[i]) {
            board[row][col] = i; // 빈칸 대입
            visited[(row - 1) / 3][(col - 1) / 3][i] = true;
            sudoku(level + 1); // 다음 빈칸
            
            if (isFinished) return;

            // 백트래킹
            board[row][col] = 0;
            visited[(row - 1) / 3][(col - 1) / 3][i] = false;
        }
    }
    
}

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            cin >> board[i][j];
            if (board[i][j] == 0) zeros.push_back(pii(i, j));
            else visited[(i -1)/ 3][(j -1) / 3][board[i][j]] = true;
        }
    }

    sudoku(0);
    
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            cout << board[i][j] << ' ';
        }
        cout << endl;
    }

    return 0;
}

스도쿠도 백트래킹의 대표 예제이다. 넣을 수 있는 후보 수들을 골라서 하나씩 넣어보며 재귀호출을 하고, 답이 나오지 않으면 다시 원래대로 돌아오면 된다.