algorithm-backtracking

💡Back Tracking?

백트래킹은 깊이 우선 탐색(DFS)를 진행하며 탐색 중인 경로에 답이 없다고 판단되면 해당 노드를 제거하고, 탐색을 시작했던 부모 노드에서 바른 방향으로 다시 탐색
여기서 더 이상 탐색할 필요가 없는 노드를 제외하는 것을 가지치기(Pruning) 이라 하고
해당 경로에 답이 있다고 판단되는 경우에는 유망하다(Promising) 라고 합니다.
 
즉, 백트래킹은 DFS탐색을 진행하며 유망한 조건을 만족하는 방향으로만 탐색하는 알고리즘!

DFS(Depth-First Search)

• 깊이 우선 탐색으로 가능한 모든 경로를 탐색 (그래프에서 깊은부분을 우선적으로 탐색)
• 모든 경로를 탐색하는 특징으로 불필요할 것 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 줄이지 못합니다.

백트래킹(BackTraking)

• 해를 찾아가는 도중에 지금의 경로가 해가 될 거 같지 않으면, 더이상 깊이 들어가지 않고 이전 단계로 다시 돌아갑니다.(가지치기)
• 불필요한 부분을 쳐내고 최대한 올바른 방향으로 나아가는 방식이기 때문에 DFS보다 효율적입니다.

🔗백트래킹 탐색 과정

♟♟문제 예시

길이가 N인 체스판 위에 N개의 퀸이 서로 공격할 수 없도록 배치할 수 있는 경우의 수는?
 

• 가지치기를 할 수 있는 경우의 수: 행, 열, 대각선
  • 가지치기를 위해 모든 경우의 수를 검사하게 되면 성능을 크게 낭비한다
  • 최대한 적은 비용으로 가지치기를 하기 위해 1차원 배열 사용
  • 배열의 index는 행의 위치, 해당 index의 value는 열의 위치
• ex) queen[2] = 1은 체스판 위에서 두번째 줄, 첫번째 칸에 해당
  • 위와 같은 데이터 형태를 잡으면 아래와 같이 잡을 수 있다
  • 한 index에 여러 value를 둘 수 없기에 행은 자연스럽게 가지치기 한다
  • index가 같다면 둘 수 없다. 같다면 가지치기
  • 행, 열에 대한 차가 같다면 대각선에 있다는 뜻이므로 가지치기
     

핵심은 가지치기!!!

결과 코드

출처

PGS 12952[N-Queen]