[c++] 백준 9663 - N-Queen(백트래킹, 재귀함수)

0. [c++] 백준

https://www.acmicpc.net/problem/9663

1. 풀이

정말 오래간만에 알고리즘 풀이를 다시 시작했다.

이번 문제는 체스판에 퀸을 배치하는 문제였다.

board라는 배열은 각 층에 배치된 퀸의 위치를 저장하였다.

모든 경로를 탐색하는 백트래킹 기법을 적용하여 퀸이 배치 가능한지 확인을 한 이후, 퀸을 배치하도록 해주었다.

각 층마다 모든 위치에 퀸을 배치해보고, 재귀함수를 활용 다음 층에서도 같은 동작을 반복하도록 하였다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

#include <iostream> #include<vector> using namespace std;   int N,ret; //배열의 순서는 행(row)을 의미하고, 담긴 데이터는 열(column)을 의미한다. int board[16];   bool check(int row, int col) {     for (int k = 1;k < row;k++) {         //보드에 놓을 퀸이 이미 배치된 퀸의 이동반경에 포함되는 경우 false를 반환하며 함수를 종료한다.         if (board[k] == col || abs(board[k] - col) == row - k) {             return false;         }     }     //퀸이 어떤 말과도 중복이 되지 않으므로 놓을 수 있다.     return true; }   //퀸을 놓는 동작을 수행한다. void takedown(int row) {     //만일 이번 퀸이 최종적인 퀸이었다면 결과를 1 증가시킨다.     if (row == N)         ret++;     else         for (int col = 1;col <= N;col++) {             if (check(row + 1, col)) {                 board[row + 1] = col;                 takedown(row + 1);             }         } }   int main() {     cin >> N;     //0을 처음에 선언하는 이유는 함수를 1~N까지 모든 경우를 탐색하게 만들어 주었는데,     //main함수에서 N번 호출하는 케이스도 가능하지만, 그 동작을 전부 takedown함수에서 수행하도록 해주었다.     //간단하게 정리하자면, 0을 제외한 (1~N,1~N)의 범위를 탐색하도록 함수를 설계한 것이다.     takedown(0);     cout << ret << endl; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!