[BOJ_9663] 백트래킹 (N-Queen)

백트래킹

 

기본적으로 백트래킹은 '가능한 모든 방법을 탐색한다' 는데 기본 아이디어가 있다. 대표적인 완전 탐색 방법으로는 DFS (Depth First Search, 깊이 우선 탐색) 이 있다. DFS 는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해서 계속 이동한다. DFS 의 장점은 무한히 깊은곳을 찾아야할때 효과적이다. 하지만 DFS 는 모든곳을 방문하기 때문에 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할수도 있다.

 

그래서 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘이다. 백트래킹은 DFS에 가지치기 (Pruning) 를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법이다. 가지치기를 얼마나 잘하느냐에 따라서 효율이 극대화 될수 있는 방법이다.

 

DFS는 가능한 모든 경로(후보)를 탐색합니다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못합니다. 따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능할 것입니다.

 

 

www.youtube.com/watch?v=ltm-JX5R1pA

 

dfs는 재귀로 문제를 푸는 것을 의미하며,

백트래킹은 break, continue를 사용하여 일부 경우의 수를 스킵하여 속도를 높이는 방법을 말한다.

 

만약 모든 경우의 수에 대해서 재귀를 통해 브루트포스 방식으로 구한 다음에 해인지 아닌지 마지막에 체크하게 되면

DFS가 되는데, N이 8인 경우 체스판의 갯수가 64개이므로 이 중에 8개를 고르는 조합의 수가 되므로 

64C8 을 하게 되면 경우의 수가 44억이 넘어갑니다.

 

가로로 겹치지 않게 한줄에 하나의 퀸만 놓는 방식으로 가지치기(백트래킹)을 하게 되면 

8^8 으로 천6백만으로 경우의 수가 줄어들게 됨.

 

가로뿐만 아니라 세로로도 겹치지 않게 permutation을 사용하는 백트래킹의 경우

8! = 40,320이 되어 경우의 수가 훨씬 줄어듭니다.

 

가로, 세로, 대각선 모두에 대해 가지치기(=백트래킹)을 사용하게 되면 5,508 정도로 훨씬 줄일 수 있습니다.

 

3'30 초부터는 내일 문제 풀고 다시 듣는걸로 합시당