[C code] 백트래킹(Backtracking ; 퇴각검색), N-Queen 문제

백트래킹은 한정 조건을 가진 문제(Constraint Satisfaction Problem ; 제약 충족 문제)를 풀려는 전략이다

이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법 !

 

브루트포스는 꼭 '깊이'나 '탐색'의 개념이 아니더라도,

모든 경우의 수를 다 대입해보는 것이기 때문에 다른 개념이다

 

조건에 맞지 않는 경우들을 배제해가며,

모든 조합을 하나씩 시도해서 문제의 해를 찾는다

 

보통 재귀 함수로 구현이 되고

DFS와 비슷하게 스택을 쓰는 경우가 많지만, 기억 공간은 덜 차지한다

 

( 아래 의사코드 11, 13 Line

 - 퇴각하며 "apply"했던 "value"를 다시 "remove"하여 돌려놓음

 -> 조건 초기화 ※중요※ )

 

의사코드는 다음과 같다

void findSolutions(n, other params) :
    if (found a solution) :
        solutionsFound = solutionsFound + 1; //Found 개수
        displaySolution();
        if (solutionsFound >= solutionTarget) : //개수 목표치
            System.exit(0);
        return

    for (val = first to last) :
        if (isValid(val, n)) :
            applyValue(val, n);
            findSolutions(n+1, other params);
            removeValue(val, n);

 

---

 

백트래킹을 이용한 문자 배열 문제를 보자

#include <stdio.h>
#include <string.h> 

void swap(char *x, char *y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 
  
void permute(char *str, int l, int r) 
{ 
   if (l == r) 
     printf("%s\n", str); 
   else
   { 
       for (int i = l; i <= r; i++) 
       { 
          swap((str+l), (str+i)); 
          permute(str, l+1, r); 
          swap((str+l), (str+i)); //백트래킹 
       } 
   } 
} 

int main() 
{ 
    char str[] = "ABC"; 
    int n = strlen(str); 
    
    permute(str, 0, n-1); 
    
    return 0; 
} 

 

Output :

ABC
ACB
BAC
BCA
CBA
CAB

 

 

그림과 같이 DFS의 방법처럼 트리를 이루어 모든 경우의 수를 탐색하는데,

퇴각할 때에 swap했던 부분을 다시 swap함으로써 다시 돌려놓음을 알 수 있다

 

-GeeksforGeeks

 

---

 

만약, 2차원 배열을 모두 해야한다면 똑같이

 

i = first to last

 j = first to last

 

하여 탐색하면 될까? 

 

이와 같은 경우는 "N-Queen 문제"와 같은데, 결과적으로는 아니다

N*N을 모두 탐색하게 되면, 수가 기하급수적으로 커져 상당한 시간이 걸리게 된다

 

즉, 다음과 같이 1차원적으로 끝낼 수 있는 방법을 고안해내야한다

 

(다음은 N*N 체스판에서 N개의 안전한 Queen을 놓을 수 있는 방법을 구현한 C언어 코드이다)

 

#include <stdio.h>

int whereQ[15]; // whereQ[a]==b is row:a, column:b
int solutionCnt;

void backtracking(int row, int N) // startN ~ N
{
    if(row > N)
        solutionCnt++;

    else
    {
        for(int i=1 ; i<=N ; i++)
        {
            if(isValid(row, i, N) == 1)
            {
                whereQ[row] = i;
                backtracking(row+1, N);
                whereQ[row] = 0;
            }
        }
    }
}

int isValid(int row, int column, int N)
{
    for(int i=1 ; i<row ; i++)
    {
        if(column == whereQ[i] || abs(row-i) == abs(column-whereQ[i]))
            return 0;
    }

    return 1;
}

int main()
{
    int N;
    scanf("%d", &N);

    backtracking(1, N);
    printf("%d", solutionCnt);

    return 0;
}

 

---

 

같은 방법으로, 스도쿠 문제의 풀이 코드는 다음과 같다

 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int board[10][10];
int whereZero[11][11];
_Bool checkSquareNum[10];
_Bool checkRowNum[10];
_Bool checkColumnNum[10];

void backtracking(int row, int idx, int column) // started row value, column value
{

    if(whereZero[row][idx] == 0)
    {
        for(int i=1 ; i<=9 ; i++) // print numbers
        {
            for(int j=1 ; j<=9 ; j++)
            {
                printf("%d ", board[i][j]);
            }
            puts("");
        }
        exit(0); // print 하면 바로 종료시킴
    }

    else
    {
        for(int i=1; i<=9 ; i++)
        {
            checkValid(row, column); // 수가 바뀔 때마다 초기화해줌
            						// (remove할 때 조건비교 가능할 수 있게)
            
            if(checkSquareNum[i] == 0 // 3*3에서의 있는 수들 check
               && checkRowNum[i] == 0 // 행에서의 있는 수들 check
               && checkColumnNum[i] == 0) // 열에서의 있는 수들 check
            {
                board[row][column] = i; // apply

                if(whereZero[row][idx+1] != 0)
                    backtracking(row, idx+1, whereZero[row][idx+1]);
                else
                    backtracking(row+1, 0, whereZero[row+1][0]);

                board[row][column] = 0; // remove
            }
        }
    }
}

void checkValid(int row, int column)
{
    checkSquare(row, column);
    checkRow(column);
    checkColumn(row);
}

void checkSquare(int row, int column)
{
    for(int i=0 ; i<10 ; i++)
        checkSquareNum[i] = 0;

    int startR;
    int startC;

    if(row <= 3)
        startR = 1;
    else if(row <= 6)
        startR = 4;
    else
        startR = 7;

    if(column <= 3)
        startC = 1;
    else if(column <= 6)
        startC = 4;
    else
        startC = 7;


    for(int i=startR ; i<=startR+2 ;i++)
    {
        for(int j=startC ; j<=startC+2 ; j++)
        {
            checkSquareNum[board[i][j]] = 1;
        }
    }
}

void checkRow(int column)
{
    for(int i=0 ; i<10 ; i++)
        checkRowNum[i] = 0;

    for(int i=1 ; i<=9 ; i++)
    {
        checkRowNum[board[i][column]] = 1;
    }
}

void checkColumn(int row)
{
    for(int i=0 ; i<10 ; i++)
        checkColumnNum[i] = 0;

    for(int j=1 ; j<=9 ; j++)
    {
        checkColumnNum[board[row][j]] = 1;
    }
}

int main()
{
    for(int i=1 ; i<=9 ; i++) // enter numbers
    {
        for(int j=1 ; j<=9 ; j++)
        {
            scanf("%d", &board[i][j]);
            if(board[i][j] == 0)
            {
                int idx = 0; // i행의 idx번째 zero의 열 : j
                while(whereZero[i][idx] != 0)
                {
                    idx++;
                }

                whereZero[i][idx] = j;
            }
        }
    }

    for(int i=1 ; i<=9 ; i++) // find first 0 & start backtracking
    {
        if(whereZero[i][0] != 0)
        {
            backtracking(i, 0, whereZero[i][0]);
            break;
        }
    }

    return 0;
}