[알고스팟/ALGOSPOT] 7. NQUEEN

 

 

 

알고리즘 알고파! 알고라파덕

안녕하세요~ 알고라파덕입니다!

이번 문제는 NQUEEN이라는 문제입니다.

재귀함수를 이용하여 백트래킹을 구현하였습니다.

• 문제 개요

 

NxN 크기의 체스판에 N개의 킨을 서로 공격할 수 없도록 올려놓는 퍼즐입니다.

 

테스트케이스가 주어지고, 테스트 케이스마다 체스판의 크기 N이 입력됩니다.

 

여기서 N개의 퀸을 배치하는 가지수를 출력해야 합니다.

 

 

• 문제 풀이

N개의 퀸을 배치해야 함으로, 한 줄에는 한 개의 퀸만이 들어가야 됩니다.

 

이를 이용하여 첫 행에 1~N열에 퀸을 배치하고 배치하였을 때 퀸의 이동경로를 체크합니다.

 

체크는 chk[][]라는 배열을 만들어 퀸의 이동경로에 포함되면 1을 아니면 0으로 입력합니다.

 

2번째 행부터 재귀함수를 이용하여 1열~N열 까지의 칸중에서 체크되지 않는 위치를 찾습니다.

 

그 후 그 칸에서 퀸이 이동하 수 있는 이동경로를 체크하고, 다음 행을 호출합니다.

 

만약에 1~N열 까지의 칸중에서 체크되어 있지 않은 칸이 없다면, 리턴을 하고, 전행에서

 

체크했었던 체크값을 다시 원상태로 돌려놓습니다. 그리고 다시 다음 열들중에서

 

체크되지 않은 곳을 찾습니다.

 

N개의 퀸을 배치하여 N번째 행을 넘어가게 된다면, 구하려는 가지 수의 개수를 증가시키고

 

리턴을 하여 다른 경우의 수도 조사합니다.

 

 

소스를 원하시는 분들은 댓글을 남겨주시고, 이해하기 어려운 분들도 댓글을 남겨주시기 부탁드립니다.

 

운행 과정을 더 자세하게 해서 올리겠습니다.

 

문제 출처 : https://algospot.com/judge/problem/read/NQUEEN