문제 출처

1. 문제설명

  • 백트래킹에서 굉장히 유명한 문제이다.
  • NxN 체스판 위에 퀸 N개를 서로 공격하지 못하게 놓는 경우의 수를 구하라.
    • 참고로 퀸은 상,하,좌,우,대각선 방향으로 공격이 가능하다.



2. 알고리즘 설계

  • 퀸이 N개가 될 때까지, 체스판의 랜덤한 위치에 놓는다.
    • 단, 공격할 수 없는 위치여야 한다.
  • 조건을 만족하면서 N개를 놓았다면 카운팅



3. 로직

  • 일반적인 dfs 조합 코드로 놓으면 된다.
  • 위치가 맞는지 체크
    • x, y 축 중 하나의 값이라도 똑같거나, (상,하,좌,우)
    • abs(x-y)가 서로 같거나 (대각선)
  • 1차원 배열로 구현 가능
    • 한 줄에 하나밖에 놓을 수 없다. (좌, 우 공격 가능)
    • 따라서 보드판의 한 행에는 무조건 하나의 퀸만 놓일 수 있다.



4. 전체 코드

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int n, ans = 0;
int queen[15];
vector<pii> v;

bool chk(int cmp) {
	for (int i = 0; i < cmp; i++)
		if (queen[cmp] == queen[i] || cmp - i == abs(queen[cmp] - queen[i]))
			return false;
	return true;
}

void dfs(int row) {
	if (row == n) {
		ans++;
		return;
	}

	for (int i = 0; i < n; i++) {
		queen[row] = i;
		if (chk(row)) dfs(row + 1);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	dfs(0);

	cout << ans;
	return 0;
}



5. 소감

  • 1차원 배열 풀이는 내가 푼 이후에 다른 사람 코드를 찾아본 것이다.
  • 원리는 단순하지만, 저걸 끌어내는 게 정말 대단한 거 같다.