[백준][C++]9663번. N-Queen

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

 

백트래킹을 사용하여 퀸의 위치를 탐색해야하는 문제이다. 한 행에서 열마다 퀸을 배치해보면서 현재 위치에 퀸을 놓을 수 있는지 검사하고 퀸을 놓고 놓을 수 없다면 skip하는 방식으로 진행한다 이 과정에서 만약 끝 행에 도달했다면 경우의 수를 하나 추가해준다. 

 

정답코드

#include <iostream>
#include <vector>

using namespace std;

int n;
int result = 0;
vector<int> board;

bool isSafe(int row, int col)
{
	//한행씩 탐색
	for (int i = 0; i < row; i++)
	{
		//같은열 | 대각선
		if (board[i] == col || abs(board[i] - col) == row - i)
			return false;
	}

	return true;
}

void solve(int row) {
    if (row == n) {     //만약 끝에 도달했다면
        result++;       //경우의 수 추가
        return;
    }

    for (int col = 0; col < n; col++) {
        if (isSafe(row, col)) { // 현재 위치에 퀸을 놓을 수 있다면
            board[row] = col;  // 퀸을 놓음
			solve(row + 1); // 다음 행으로 진행
        }
    }
}

int main()
{
	cin >> n;
	board.resize(n);
	solve(0);

	cout << result << "\n";

	return 0;
}