[알고리즘] Backtracking

Backtracking

미로찾기

• 막다른 골목이면 이제까지 온 길을 돌아오게 된다. (백트레킹 -> 스택 & 재귀?)
• right hand / left hand -> 오른손(왼손)으로 벽을 짚고 간다.(출구가 중간에 있으면 안될 경우도 생김)

N-Queen

• NxN 크기의 체스판에서 퀸을 같은 행, 같은 열, 같은 대각선 위에 놓지 않을 수를 구하기.
• 문제 해법
• 4개의 퀸을 모두 다른 행에 놓으면서 해가 되는 퀸의 열의 위치가 어디인지 계산
• Candidate 해
  • 모두 다른 행에 대한, 가능한 모든 열의 조합
  • [(1,1),(2,1),(3,1),(4,1)], ..... , [(1,4),(2,4),(3,4),(4,4)] => 4-퀸 = 4 4 4 * 4 해의 개수 (n^n)
  • State-Space Tree : 모든 후보해를 포함, 각 노드에는 한 개 퀸의 위치를 나타냄, Tree의 루트노드부터

       단말노드까지의 각 노드의 위치의 합이 한개의 후보해를 나타냄(끝까지 온다면 가능)

  • Backtracking : state-space tree의 어떤 노드에서 더이상 해를 구하지 못하면 그 노드(non-promising)의 부모로 GO
  • Pruning : non-promising 이면 부모로 GO, promising이면 계속 진행. ```C++ if(col[row]==col[k] || abs(col[row]-col[k] == row-k) //행과 열의 차이가 같다면 대각선임으로 0리턴..

```

1. N-QueenCode

knight's Tour

• 임의의 위치에 놓여진 기사말을 움직여서 64개의 격자를 모두 방문할 수 있는 수. 다시 방문X
• 갈 수 있는 위치 : (i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2),(i-1,j-2),(i-2,j-1) 8방향
• 8->8->8->..... 한 노드에 8 개씩... 8개가 다 갈 수 없으면 부모노드로 Go