백트레킹
-
[알고리즘] BacktrackingSW/Algorithm 2018. 1. 6. 21:00
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 : 모든 ..