[알고리즘] 백트래킹

• 공부한 날짜: 2021. 11. 10 / 전체 1차 공부 끝!!!!

 

1. 백트래킹

: 여러 후보해 중에서 특정 조건을 충조고시키는 모든 해를 찾는 알고리즘 

백트래킹이 다루는 문제들은 해가 하나 이상 존재한다

후보해: 해가 될 수 있는 가능성을 가진 부분해의 조합

모든해: 문제의 정답을 모아놓은 것

목적: '진짜 해'를 효율적으러 찾는 것 

 

2. 백트래킹을 이용한 미로찾기 

 

• 규칙

ㄱ. 갈래 길이 나오면 무조건 왼쪽 길부터 들어간다

ㄴ. 막다른 곳이 나오면 갈래 길목으로 되돌아 나와 다음 길을 시도한다

ㄷ. ㄱ~ㄴ 과정을 목표 지점에 도달하거나 모든 경로를 다 탐색할 때까지 계속한다

 

• 깊이 우선 탐색과 다른점

: 깊이 우선 탐색은 모든 노드를 방문하는 것이 목적이고, 백트래킹은 해를 찾는 것이 목적이기 때문에 모든 노드를 방문할 필요가 없다

(해를 찾는 비용을 줄이기 위해 최대한 방문할 노드의 수를 최소화하는 것이 중요)

 

• 구현 원리

(1) 부분해 계산 

(2) 다음 부분 후보해 목록 확인(여기서 재귀호출을 이용한다)

(3) 각 부분 후보해 계산 

 

• 백트래킹이 처리해야하는 경우

(1) 현재 시도 중인 부분 후보해가 해가 될 수 있는 조건을 불만족 시킬때

(2) 최종해를 확보한 경우 (후보해가 조건을 만족한 경우)

 

백트래킹 구현방법: 위의 두가지 경우를 만나면 그 함수를 반환하는 것으로 백트래킹이 이루어진다 

 

 

• 알고리즘 구현 

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

ㄴ. 현 위치에서 가고자 하는 방향에 대해 이동 가능한지를 확인. 벽과 지나왔던 길은 이동가능한 길이 아님

ㄷ. ㄴ 과정에서 현재 방향에 대해 이동가능한 방향임이 확인되면 그곳으로 이동. 이동이 불가능한 방향으로 판정되면 방향(북-님-동-서)을 바꾸어서 다시 ㄴ을 시행한다. 현 위치에서 어떤 방향으로도 이동할 수 없ㅇㅁ이 확인되면 이전 위치로 되돌아감

ㄹ. 출구를 찾거나 미로 내의 모든 길을 방문할 때까지 ㄴ,ㄷ과정을 반복 

 

*ㄴ과정은 GetNextStep(),ㄷ과정은 MoveTo()라는 함수로 구현함 

 

 

2. N개의 퀸

: 퀸 N개를 NxN 크기의 체스판 안에 서로를 공격할 수 없게 배치하는 모든 경우를 구하는 문제