백트래킹이란!
말 그대로 모든 경우의 수를 하나하나 모두 방문해서 계산하는 방식을 말한다.
이거 처음 배울때는 진짜 ㅈ같았는데 동적문제 들어가니까 이게 좋았던걸 알았다...
예전에 다녔던 정올 학원에서 어떤 꼬맹이가 백트래킹 배우면서 어렵다고 징징대니까 다이나믹 공부하는 학생들이
부럽다는 시선으로 쳐다보고 선생님이 웃으셨던 기억이 난다 ㅋㅋ;;
대표적인 알고리즘으로는 N퀸 문제가 있다.
숫자 N이 주어지면 N x N 의 체스판에서 퀸이 서로를 잡을 수 없게 최대 몇개까지 배치할 수 있는지 뭍는 문제이다.
퀸은 가로세로 대각선을 칸 수 제한없이 잡으므로 각각의 행마다 하나씩 배치하면서 조건에 만족하는지 검사하고 현재 행 수가 주어진 N을
초과한다면 트레이스를 종료하는 종류의 문제가 되겠다.
#include <stdio.h>
#include <stdlib.h>
#define N 15
int arr[50][50]; // 퀸 위치 출력용 배열
int ch[50]; // 퀸 위치 검사용 배열
void r(int q) {
if(q == N) { //각 행마다 하나의 퀸을 놓으며 마지막 열번호(N - 1)을 넘어가면 검사가 끝난다.
for(int i = 0; i<N; i++) {
for( int j = 0; j<N; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
exit(0); // 출력하고 종료
}
//x축 : 행번호 y축 : 열번호
int sign = 0;
for ( int i = 0; i < N; i++) { //
sign = 0;
for( int j = 0; j < q ; j++ ) { // 이 부분이 좀 헷갈릴 수 도 있는데 j는 행번호가 아니고 열번호다 행번호는 ch[j]임
if( ch[j] == i ) { // 같은 열에 있으면 검사 종료
sign = 1;
break;
}
if( abs(ch[j] - i) == abs(q - j) ) { // 대각선 검사 : x1- x2의 절댓값과 y1-y2의 절댓값이 같다면 같은 대각선임
sign = 1;
break;
}
}
if(sign == 1) continue; // 검사 결과 다르다면 새로운 퀸 위치를 생성함
ch[q] = i;
arr[q][i] = 1; // 검사용배열과 출력용 배열에 퀸 위치를 기록하고
r(q+1); //다음 행 검사로 출발
arr[q][i] = 0;
ch[q] = 0;
}
}
int main() {
r(0);
return 0;
}
위의 재귀호출을 보면 별다른 유추 과정 없이 그냥 N x N의 모든 칸에 퀸을 놓아보고 맞으면 진행 틀리면 다시 돌아가는 과정을 무한 반복하고 있다.
이러한 특성 덕분에 머리 비우고 코딩 하기 딱 좋은 알고리즘이다. 문제가 요구하는 부분만 파악 할 수 있다면 대부분 아주 쉽게 풀 수 있다.
그리고 대충 예상 했겠지만 모든 경우의 수를 돌아본다는 특성 때문에 시간제한에 매우 많이 걸리는 문제이기도 하다...
예전에 순x향대 ctf 소수구하는 문제였나? 그 문제3번에서 다 풀었는데 시간제한이 자꾸 몇초씩 나가서 4위까지 갔다가 떨궜던 기억이 난다...
(사실 떨어진 건 딴 이유지만.. ㅎㅎ)