백준 9663번: N-Queen (C++)

문제 링크 : www.acmicpc.net/problem/9663

 

 

단순 백트래킹 문제다.

그냥 무작정 다 배치한 다음 확인을 하면 n^n이라는 어마어마한 시간복잡도가 나오게 된다.

결국 백트래킹을 사용해야한다.

 

 

 

<전체적인 알고리즘>

1. 한 줄씩 queen을 놓아본다.

2. queen을 놓을 수 없는 상황이오면 바로 돌아간다.(백트래킹)

 

 

 

 

<전체코드>

#include<iostream>
#include<vector>

using namespace std;

vector<pair<int, int>> queen;
int n;
int result = 0;

bool can_exist(int x,int y)  //해당 위체에 queen놓을 수 있는지
{
	for (int i = 0; i < queen.size(); i++)
	{
		int x2 = queen[i].first;
		int y2 = queen[i].second;
		if (x == x2 || y == y2 || abs(x - x2) == abs(y - y2))return false;
		//대각선이나 직선에 다른 queen이 있으면 존재 불가능, false 반환
	}
	return true;
}

void dfs(int x)
{
	if (x < 0)
	{
		result++;
		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (can_exist(x, i))  //놓을 수 있으면
		{
			queen.push_back(make_pair(x, i));  //놓고
			dfs(x - 1);   //그 다음 줄 ㄱㄱ
			queen.pop_back();  
		}	
	}
}


int main()
{
	cin >> n;

	dfs(n-1);

	cout << result << "\n";

	return 0;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.