[알고리즘] Backtracking (백트래킹)

출처:http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Backtracking-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

백트래킹

정의 : 여러 해들 중에 조건에 맞는 모든 해를 찾는 알고리즘.

알고리즘

1. 후보 해를 선택한다.

2. 조건에 따라 후보 해에 적절성 검사를 시행한다. 통과하지 못하면 지금 현재 선택한 후보 해를 버리고 1로 돌아가 후보 해를 다시 선택한다.

3. 적설성 검사가 통과한 경우 이 후보 해가 문제의 해가 되는지 검사한다. 검사를 통과하면 이것이 문제의 해이고, 검사를 통과하지 못하면 1로 돌아가 후보 해를 계속해서 선택한다.

백트래킹의 활용

1. 미로 탈출로 찾기

재귀함수를 통해 백트래킹으로 미로 탈출로를 찾아보자. 

알고리즘

1. 시작점을 현재 위치로 지정하고, 이동방향을 북으로 설정한다.

2. 현재 위치에서 가고자 하는 이동 방향으로 이동이 가능한지 확인한다. 벽과 이미 지나온 길은 이동가능한 길이 아니다.

3. 현재 가고자 하는 이동 방향으로 이동이 가능하면 그곳으로 이동한다. 이동이 불가능하면 방향을 바꾸어 다시 2번을 수행한다. 모든 방향으로 이동이 불가능하면 이전 위치로 되돌아간다.

4. 출구에 다다르거나 미로 내의 모든 길을 방문할때까지 2, 3단계를 반복한다.

3번 과정에서 이동하는 부분을 재귀함수로 구현하면 될 것이다. 이동이 가능하면 재귀함수를 통해 그곳으로 이동하면 모든 방향으로 이동이 불가능하면 반환을 통해 재귀함수를 탈출하여 이전 상태로 돌아가면 될 것이다.

2. N개의 퀸

체스에서 퀸은 모든 방향으로 거리 제한없이 움직일 수 있는 말이다. N개의 퀸 문제는 N × N 크기의 체스판에서 N개의 말들이 서로 공격이 불가능하게 배치하는 모든 경우를 구하는 문제이다. 

알고리즘

1. 첫 행, 첫 열을 시작점으로 지정한다.

2. 현재 지점에서 퀸을 놓으면 다른 퀸에게 위협을 받는지 검사한다. 이전 단계에서 놓은 퀸들 중에 현재 지점에서의 퀸의 행 값이 같으면 수평방향으로 위협을 받는 것이고, 열 값이 같으면 수직방향으로 위협을 받는 것이다. 행의 차와 열의 차가 같으면 대각선 방향으로 위협을 받고 있는 것이다.

3. 위협을 받고 있지 않다면 행의 값을 증가시키고 열의 첫번째 값으로 가서 2를 수행한다. 위협을 받고 있다면 열의 값을 증가시켜서 2를 수행한다. 열의 마지막 값에서도 위협을 받고 있다면 이전 단계의 퀸의 위치로 되돌아간다.

4. 마지막 행, 마지막 열에 다다르면 종료한다.

과정 3을 재귀함수로 구현하면 될 것이다.