백 트래킹 ( Backtracking )

1. 개요

[그림 1] 백 트래킹(Backtracking) 과정

 백트래킹의 주요 개념은 해를 얻을 때까지 모든 가능성을 시도하는 기법이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에서 해결책을 찾는다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아가고 시도해보지 않은 다른 해결 방법이 있으면 시도한다. 여러 시도중 해결 방법이 더이상 없으면 더 이전의 분기점으로 돌아가고 모든 트리의 노드를 검사해도 답을 찾지 못할 경우, 이 문제의 해결책은 없는 것으로 간주한다.

1. 어떤 노드의 유망성을 점검한 후에 유망(Promising)하지 않다고 결정되면 그 노드의 부모로 돌아가 (backtracking) 다음 자식 노드로 감

2. 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없다면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다.

3. 가지치기 (pruning) : 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다.

---

2. 백트래킹 예제 1 - 보글게임

[그림 2] 보글게임

N X M 크기의 알파벳 격자에서 상하좌우 / 대각선 으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 게임

※ 입력 : 정수 N,M은 1<= N <= 100, 1<= M <= 1000의 크기를 갖는다.

1. main()

int main() { FILE *fp; int res; /* 단어 검색 성공 시 1, 실패 시 0 저장 */ char *searchWord[] = {"PRETTY", "LGE", "ASDVX"}; int count=0; /* 게임 횟수 누적변수 */ fp=fopen("d:\\data\\boggleGame.txt", "rt"); assert(fp != NULL); while(initBoard(fp)) { res = boggleGame(searchWord[count]); /* 보글 게임 함수 호출 */ if(res == TRUE) /* 단어를 찾았으면 */ printf("+ Existence!!(%s)\n", searchWord[count]); else /* 단어를 못찾았으면 */ printf("- Nonexistence!!(%s)\n", searchWord[count]); ++count; } fclose(fp); return 0; }

FILE 입출력 함수를 이용해 단어가 저장된 텍스트파일을 불러오고 검색할 단어 배열을 선언

반복문을 이용해 보드 2차원배열에 텍스트파일 하나씩 저장한다.

2. 판 초기화 및 게임구동 함수

/*-------------------------------------------------------------------------------------- 함수명 및 기능: initBoard() - 파일에서 보글 게임의 board정보를 입력 받아 초기화하는 함수 전달인자 : fp - board정보를 저장하고 있는 파일의 파일 포인터 리턴값: board정보를 정상적으로 초기화 하면 1리턴, 실패하면 0 리턴 --------------------------------------------------------------------------------------*/ int initBoard(FILE *fp) { int i; /* iterator */ fscanf(fp, "%d %d\n", &maxY, &maxX); /* 문자의 가로 개수와 세로 개수 읽기 */ if(maxY==0 || maxX==0) return FALSE; /* 가로 또는 세로 크기가 0이면 초기화 실패 */ for(i=0; i< maxY; ++i) { fgets(board[i], maxX+2, fp); /* 개행문자와 널문자의 크기 고려해서 +2 */ board[i][maxX]='\0'; /* 함께 읽혀들어온 한 줄 뒤의 개행문자 삭제 */ puts(board[i]); /* 읽어들인 배열 출력 */ } return TRUE; /* board 초기화 성공 */ } /*-------------------------------------------------------------------------------------- 함수명 및 기능: boggleGame() - board에 전달된 문자열이 있는가 검사하는 함수 전달인자 : searchWord - 검색할 단어문자열의 시작주소 리턴값: board에 찾는 문자열이 있으면 1리턴, 없으면 0리턴 --------------------------------------------------------------------------------------*/ int boggleGame(const char *searchWord) { int i,j; /* iterator */ int res; /* 단어 검색 성공여부 저장 */ for(i=0; i<maxY; ++i) { for(j=0; j<maxX; ++j) { res = hasWord(i, j, searchWord); /* 배열 전체의 각 방을 단어 검색 시작점으로 설정하여 반복 호출 함 */ if(res == TRUE) /* 단어를 찾았으면 바로 TRUE 리턴 */ return TRUE; } } return FALSE; }  

 3. 단어 찾기 ( 백트래킹 )

/*-------------------------------------------------------------------------------------- 함수명 및 기능: hasWord() - 전달된 y, x 좌표에 찾는 문자가 존재하는가 검사하는 재귀함수 전달인자 : y - 검사할 y 좌표 x - 검사할 x 좌표 word - 검사할 문자열의 시작주소 리턴값: 해당좌표에 찾는 문자 있으면 1리턴, 좌표가 유효하지 않거나 찾는 문자 없으면 0리턴 --------------------------------------------------------------------------------------*/ int hasWord(int y, int x, const char * word) { int i; /* iterator */ int nextY; /* 다음에 검사할 Y좌표 저장 */ int nextX; /* 다음에 검사할 X좌표 저장 */ if( !inRange(y,x) ) /* 기본 부분(Basis part) 1 : 시작 위치가 범위 밖이면 실패 */ return FALSE; if(board[y][x] != word[0]) /* 기본 부분(Basis part) 2 : word문자열의 첫 글자가 x, y 좌표의 내용과 일치하지 않으면 실패 */ return FALSE; if(strlen(word)==1) /* 기본 부분(Basis part) 3 : 단어의 길이가 1이면 성공 <== 기본 부분 2보다 반드시 나중에 검사해야 함 */ return TRUE; for(i=0; i<8; ++i){ /* 8방향에 대해 이어지는 스펠링이 존재하는가 검사 */ nextY = y + RCXY[i].y; nextX = x + RCXY[i].x; if(hasWord(nextY, nextX, word+1)) return TRUE; } return FALSE; }

재귀호출을 사용하여 구현하였다. 기본부분 (Base Part) 는 종결 조건이 3가지 이므로 3개를 설정했다. 하나는 시작위치가 판의 범위의 벗어났을 때 하나는 Word 문자열의 첫 글자가 현재 x,y좌표랑 일치하지 않을 경우 마지막 하나는 단어의 길이가 1이면 TRUE를 리턴하면서 종료하는 것이다. 

단어의 길이가 1인 이유는 만약 Word문자열의 첫 글자가 x,y좌표랑 일치하여 팔방재귀를 하면서 다음 검사를 하게된다고 하자 

[그림 2]를 예로들면 찾는 단어가 "PRETTY" 이므로 Word문자열의 첫 글자는 1행 4열의 "P"가 될 것이다. 그림에서는 2행 2열의 "P"가 빨간색으로 돼있지만 이 코드에서는 팔방재귀 즉, 대각선도 검사하므로 1행 4열의 "P"가 선택이 될 것이고 다음 2행 3열의 R ... 2행 4열의 E..이런식으로 재귀호출시 전달인자로 Word배열 + 1 을 주어서 단어의길이가 1이 될때 종료를 시킨다. 

---

3. 백트래킹 예제 2 - N Queen

[그림 3] N Queen 문제

N * N 체스 보드판에 N개의 queen을 서로 공격하지 못하도록 배치하는 방법을 찾아내는 문제.

입력 : 정수 n을 입력한다  ( 1<=N<=15 )

출력 : 서로 총 경우의 수를 출력한다.

[해결법]

이 문제를 풀기위해선 퀸의 공격범위에 대해 생각을 해야한다.

퀸이 공격할수 있는 루트는 상하좌우/대각선 이동이 가능하고 판의 끝까지 갈 수 있다. 따라서 생각해보면 한 행에 하나 이상의 퀸을 놓을 수 없다는 성질, 예를들어 4*4 의 체스판에서 화살표가 지나간 칸에는 퀸을 놓을 수 없다는 성질을 고려한다.

[그림 4] 4*4판에서의 퀸의 공격방향

1. 첫 번째 행, 첫 번째 열에 퀸을 놓는다.

2. 다음 행에서 가능한 가장 왼쪽 열에 퀸을 놓는다.

3. N번째 열에 더 이상 퀸을 놓을 수 없다면 백트랙 한다.

4. 마지막 행에 퀸을 놓으면 하나의 해를 구한 것이다.

5. 모든 경우를 조사할 때까지 백트래킹하며 해를 구함.

행은 검사할 필요가 없으므로, 열과 대각선만 검사하면 된다. 열을 검사하는 방법은 크기가 N 인 체크 배열을 만들어 K번째 열에 퀸을 놓았다면 배열의 K번째 위치를 체크하여 이후의 행에서는 체크된 열에 퀸을 놓지않게 한다.

열과 마찬가지로 대각선도 체크배열을 통해 판별한다.

/*------------------------------------------------------------------ 함수명 및 기능: nQueen() - n개의 queen을 배치하기 위한 재귀호출 함수 전달인자 : row - 체스판의 행번호(0행은 사용 안함) 리턴값: 없음 ------------------------------------------------------------------*/ void nQueen(int row) { int i; /* n이 4일때 좌표계산법 (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4) (1,1) 대각선은 incDiagonalLineChk[2] 방에 체크 <<== (행+열) = 1+1 = 2번방 (2,1) (1,2) 대각선은 incDiagonalLineChk[3] 방에 체크 (3,1) (2,2) (1,3) 대각선은 incDiagonalLineChk[4] 방에 체크 (4,1) (3,2) (2,3) (1,4) 대각선은 incDiagonalLineChk[5] 방에 체크 ... (1,4) 대각선은 decDiagonalLineChk[1] 방에 체크 <== n+(행-열) = 4+(1-4) = 1번방 (1,3) (2,4) 대각선은 decDiagonalLineChk[2] 방에 체크 (1,2) (2,3) (3,4) 대각선은 decDiagonalLineChk[3] 방에 체크 (1,1) (2,2) (3,3) (4,4) 대각선은 decDiagonalLineChk[4] 방에 체크 ... */ /* for(int j=1;j<=n;++j) printf("%4d", columnChk[j]); printf("\n"); */ if(row>n) // 행값이 n을 초과하면 퀸을 서로 공격못하게 배치하는 작업이 1회 끝난 것이므로 { placementCnt++; // 배치 카운트를 증가시키고 return; // backtrack } for(i=1; i<=n; ++i) { if(!columnChk[i] && !incDiagonalLineChk[row+i] && !decDiagonalLineChk[n+(row-i)]) { columnChk[i] = incDiagonalLineChk[row+i] = decDiagonalLineChk[n+(row-i)] = CHECK; // 퀸 배치 nQueen(row+1); // 현재 행이 가능하므로 다음 행을 검사하기 위해 재귀호출 함 columnChk[i] = incDiagonalLineChk[row+i] = decDiagonalLineChk[n+(row-i)] = 0; // backtrack 후 체크했던 내용 삭제 } } return; } /* 실행결과 n= 1 배치가능 경우 = 1 n= 2 배치가능 경우 = 0 n= 3 배치가능 경우 = 0 n= 4 배치가능 경우 = 2 n= 5 배치가능 경우 = 10 n= 6 배치가능 경우 = 4 n= 7 배치가능 경우 = 40 n= 8 배치가능 경우 = 92 n= 9 배치가능 경우 = 352 n=10 배치가능 경우 = 724 n=11 배치가능 경우 = 2680 n=12 배치가능 경우 = 14200 n=13 배치가능 경우 = 73712 n=14 배치가능 경우 = 365596 n=15 배치가능 경우 = 2279184 */

첫번째로 1행1열에 퀸을 놓고 

열 체크배열 1번방에 체크 , 증가대각선 체크배열 (1 + 1) = 2 번방에 체크, 감소대각선 체크배열 ( n=4  + (1-1) ) = 0번 방에 체크한다

다음 행을 하나 증가시켜 재귀호출을 하며 똑같은 과정을 반복한다.

4*4판의 경우 1행1열에 퀸을 놓았을때는 해가 안나온다 따라서 백트랙,백트랙 하여 이전에 체크했던 내용을 삭제하고 맨 처음으로 돌아가

2행 1열에 퀸을 놓으면서 다시 시작한다.

[출력 예시]