알고리즘 강좌 7회

  

백 트래킹

 

백 트래킹(Backtracking : 되추적)의 개념부터 살펴보자.

백트래킹을 한마디로 말하자면... “몽땅 다 찾아본다” 라는 말로 요약이 가능하다. 여기다 살을 조금 붙이면 “답에 될 수 있는 것을 몽땅 다 찾아본다” 라는 말로 확장할 수 있다. 백트래킹의 개념은 이 말 그대로다. 답이 될 만한 것들을 모두 다 뒤져봐서 그 중에서 답을 찾는 알고리즘이 바로 백트래킹이다.

 

이러한 백트래킹은 몇가지 특징을 가진다.

1. 함수의 재귀호출을 이용해 구현한다.

2. 모든 가능성을 몽땅 뒤져보는 것이기 때문에, 대체로 수행하는데 시간이 오래 걸린다.

3. 모든 가능성을 몽땅 뒤져보는 것이기 때문에, 백트래킹으로 풀 수 없는 문제는 별로 없다.

이 특징들을 대충 살펴보자.

1번에 나온 것처럼 백트래킹은 재귀호출을 이용해 구현하는 경우가 대부분이다. 이것은 재귀호출이 백트래킹을 구현하기에 매우 편리하기 때문이다. 또한 2번 특징의 경우 너무나 당연한 결과라고 할 수 있겠다. 어떤 문제든, 보통 답이 될 수 있는 후보(이걸 후보해라고도 한다)는 굉장히 많다. 백트래킹은 이걸 모두 뒤져보기 때문에, 다른 알고리즘에 비해 수행시간이 오래 걸릴 수밖에 없다. 일반적으로 어떤 문제의 후보해는 문제의 크기(n)에 비례한다.

3번 특징이 많은 사람들이 백트래킹을 쓰는 가장 큰 이유이다. 거의 모든 문제가 백트래킹으로 풀린다고 봐도 무방할 정도이다. 이런 특징 때문에 각종 컴퓨터 경시대회 시험장에서 툭하면 쓰이는 게 백트래킹이다.(필자도 시험장에서 문제를 받아 들었을 때 모르겠다 싶으면 무조건 백트래킹 돌렸다--;) 하지만 백트래킹을 써야만 풀리는 문제들도 많이 있다. 다음 절부터는 이런 문제들을 중심으로 백트래킹을 설명해 나갈 것이다.

[미로탐색문제]

 한번쯤은 해보았을만한 미로 탐색문제이다.

0은 이동이 가능한 길이고 1은 벽이다.

대각선으로는 이동이 불가능하다.

0	0	1	1	0		0	0	1	1	0
1	0	0	0	0		1	0	0	0	0
1	0	1	0	1		1	0	1	0	1
0	0	0	1	0		0	0	0	1	0
0	1	0	0	0		0	1	0	0	0

 

0,0은 시작점이고 4,4는 도착지점이 된다. 0,0에서부터 출발하여 4,4까지 도달할 수 있는 모든 가지 수를 출력하는 프로그램을 작성하여라.

위와 같이 한 가지 길만이 존재한다.

DFS 탐색으로 0,0에서부터 4,4까지 모든 점을 탐색하여본다.

DFS 탐색이란 깊이우선탐색이라고 부르며 4방향을 검사하여 진행할 수 있다면 계속하여 진행하는 방식을 의미한다. 위의 그림에서 보면 0,0에서 진행할 수 있는 방향을 검사해보면 오른쪽이 나온다.

그럼 오른쪽으로 이동 후에 다시 이동할 수 있는 길을 보면 아래쪽만이 존재한다. 그럼 아래쪽으로 진행 후에 살펴보면 오른쪽과 아래쪽이 있다. 기본적으로 오른쪽, 아래, 왼쪽, 위 순서로 검사를 한다면 오른쪽으로 이동할 것이다. 그럼 계속해서 진행하면 1,4의 좌표에서 위쪽으로 진행이 가능하므로 위로 올라가게 된다. 위쪽에서는 더 이상 진행이 불가능하므로 갈림길이 생겼던 1,3으로 이동하게 된다. 여기서 아래쪽으로 이동하게 되면 더 이상 진행이 불가능하므로 1,1의 갈림길로 이동하게 된다. 다시 아래쪽으로 계속하여 진행하면 1,3의 지점에서 오른쪽으로 진행(왼쪽으로 진행하지 않는 이유는 검색방향이 오른쪽, 아래, 왼쪽, 위 순서대로 빽트래킹으로 검색을 하기 때문이다. 계속해서 진행하면 마지막 좌표까지 가게 된다. 이때 프로그램이 종료되면 안 되고 다른 곳으로도 이동이 가능한지 검사해야 된다.

 

<입력값>	<출력값>
5 0 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0	1

 

 

<프로그램소스>

#include <stdio.h>

 

int n;

int map[4][4];

int cnt;

 

void input()

{

int i,j;

FILE *in;

in=fopen("input.txt","r");

fscanf(in,"%d\n",&n);

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

fscanf(in,"%d",&map[i][j]);

}

}

}

 

int back(int i,int j)

{

if(map[i][j]!=0 || i>=n || j>=n || i<0 || j<0) return 0;

map[i][j]=2;

if(i==n-1 && j==n-1)

{

cnt++;

map[i][j]=0;

return 0;

}

back(i,j+1);

back(i+1,j);

back(i-1,j);

back(i,j-1);

map[i][j]=0;

}

 

void main()

{

input();

back(0,0);

if(cnt!=0) printf("%d\n",cnt);

}