[알고리즘] 백트래킹(Backtracking) - 코딩밥상
백트래킹(Backtraking)이란?
백트래킹은 여러 후보 중 특정 조건을 충족시키는 모든 해를 찾는 알고리즘입니다. DP나 그리디(Greedy) 알고리즘이 풀 수 있는 문제의 유형이 따로 있듯이 백트래킹 역시 그렇습니다.
백트래킹이 다루는 문제들은 해가 하나 이상 존재합니다. 이때 그 해들을 일컬어 '모든 해'라고 합니다. 해를 구하는 과정에서 해가 될 수 있는 가능성을 가진 부분해의 조합을 '후보 해'라고 합니다.
백트래킹이 다루는 문제들은 후보해의 수가 굉장히 많다는 특징이 있습니다. 이 중에서 해가 될 조건을 만족시키는 '진짜 해'를 효율적으로 찾는 것이 백트래킹의 목적입니다.
백트래킹이 다루는 문제들은 다양한 후보해를 갖고 있기때문에 대부분 트리의 형태로 표현할 수 있습니다. 따라서 해를 찾는 비용을 줄이기 위해 방문할 노드의 수를 최소화하는 것이 중요합니다.
후보해 속에서 해를 찾는 과정을 정리해보면 다음과 같습니다.
- 뿌리 노드에서 출발
- 현재 위치한 부분해에서 선택 가능한 다음 부분해의 목록을 기반
- 부분해의 목록을 하나씩 방문
- 방문한 부분해가 '해가 될 수 있는 조건'을 만족시키면 진행, 그렇지 않으면 이전 부분해로 돌아 나와(Backtraking) 다른 부분해로 시도
- 최종해를 얻거난 모든 경우의 수를 확인할 때까지 반복
대표적인 백트래킹 알고리즘을 활용하는 문제로 '미로 찾기' 문제가 이에 해당합니다.
미로찾기 문제
먼저 미로의 탐색 규칙을 정해보겠습니다.
- 갈림길이 나오면 무조건 왼쪽 길부터 탐색
- 막다른 곳이 나오면 갈라진 길목으로 되돌아 나와 그 다음 길을 시도
- 목표 지점에 도달하거나 모든 경로를 다 탐색할 때까지 반복
이 규칙을 따라 미로를 탐색해보면 트리의 형태로 나타낼 수 있습니다. 길이 이어져있으면 그대로 자식 노드로 연결하고, 막다른 길은 잎 노드가 되는것입니다.
하지만 위 방법은 논리적인 개념이지 물리적인 존재의 해를 구하는 것이 아닙니다. 즉 복잡한 트리 자료구조 없이 미로 탈출 알고리즘을 구현할 수 있습니다. 그 방법엔 여러가지가 있겠지만 구현이 가장 간편한 재귀 호출을 이용할 수 있습니다.
위 미로 탐색의 과정은 백트래킹 알고리즘의 측면에서도 똑같이 '부분 해 계산' -> '다음 부분 후보해 목록 확인' -> '각 부분 후보해 계산의 반복'으로 이루어 지기때문에 이는 재귀 호출과 어울리는 것입니다.
여기서 백트래킹(되돌아 나오기)을 처리해야 하는 경우는 '현재 시도 중인 부분 후보해가 조건을 만족하지 못했을 때와 최종해를 확보한 경우' 두 가지입니다. 상위 부분해가 호출한 후보 부분해의 재귀 함수에서 다음 두 조건을 만나면 그저 함수를 반환하는 것만으로 백트래킹이 이루어집니다. 상위 부분해를 시도 중인 함수로 제어 흐름이 돌아가기 때문입니다.
알고리즘 정리
- 시작점 을 현재 위치로 지정하고 이동 방향을 북으로 설정
- 현 위치에서 가고자 하는 방향으로 이동 가능 여부 확인
- 이동 가능하다면 이동, 이동 불가능하다면 (북-남-동-서 순)방향을 바꿔 다시 확인 네 방향 모두 불가능하다면 백트래킹
- 출구를 찾거나 모든 길을 방문할 때까지 반복
typedef struct tagMazeInfo{
int ColumnSize;
int RowSize;
char** Data;
}MazeInfo;
typedef struct tagPosition{
int X;
int Y;
}Position;
enum DIRECTION {NORTH, SOUTH, EAST, WEST};
enum RESULT {FAIL, SUCCEED};
int GetNextStep(MazeInfo* Maze, Position* Current, int Direction, Position* Next){ //다음 블록의 조건 확인
switch (Direction) {
case NORTH:
Next->Y = Current->Y-1;
Next->X = Current->X;
if(Next->Y == -1) return FAIL;
break;
case SOUTH:
Next->Y = Current->Y+1;
Next->X = Current->X;
if(Next->X == Maze->ColumnSize) return FAIL;
break;
case EAST:
Next->Y = Current->Y;
Next->X = Current->X+1;
if(Next->X == Maze->ColumnSize) return FAIL;
break;
case WEST:
Next->Y = Current->Y;
Next->X = Current->X-1;
if(Next->X == -1) return FAIL;
break;
}
if(Maze->Data[Next->Y][Next->X] == 'x') return FAIL;
if(Maze->Data[Next->Y][Next->X] == 'm') return FAIL;
return SUCCEED;
}
int MoveTo(MazeInfo* Maze, Position* Current, int Direction){ //다음 블록으로 이동
int Dirs[] = {NORTH, SOUTH, EAST, WEST};
Position Next;
if(Maze->Data[Current->Y][Current->X] == 'G') return SUCCEED;
for(int i=0; i<4; i++){
if(GetNextStep(Maze, Current, Dirs[i], &Next) == FAIL) continue;
if(MoveTo(Maze, &Next, NORTH) == SUCCEED) return SUCCEED;
}
Maze->Data[Current->Y][Current->X] = 'W';
return FAIL;
}
int Solve(MazeInfo* Maze){
int StartFound = FAIL;
int Result = FAIL;
Position Start;
for(int i=0; i<Maze->RowSize; i++){ //시작점 찾기
for(int j=0; i<Maze->ColumnSize; j++){
if(Maze->Data[i][j] == 'S'){
Start.X = j;
Start.Y = i;
StartFound = SUCCEED;
break;
}
}
}
if(StartFound == FAIL) return FAIL;
if(MoveTo(Maze, &Start, NORTH)) Result = SUCCEED;
else if(MoveTo(Maze, &Start, SOUTH)) Result = SUCCEED;
else if(MoveTo(Maze, &Start, EAST)) Result = SUCCEED;
else if(MoveTo(Maze, &Start, WEST)) Result = SUCCEED;
Maze->Data[Start.Y][Start.X] = 'S';
return Result;
}