[Cpp][백준 9663][💛골드 5] N-Queen (백트래킹)

🧞‍♂️ 난이도

💛 골드 5

🧞‍♂️ 문제

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

🧞‍♂️ 내 풀이

🔥 첫 번째 풀이 ❌ (시간초과)

프로그래머스의 N-Queen도 있네.. 이거 파이썬으로는 거의 불가능한것 같다

🧞‍♂️ C++ 코드

#include <bits/stdc++.h>

using namespace std;

int N, answer;
int queen[15]; // 인덱스는 row 가 된다. row 별 어느 col 에 두었는지 그 col 값을 기록.

void dfs(int row) {
	if (row == N) {
		++answer;
		return;
	}
	
	for (int col = 0; col < N; ++col) {
		queen[row] = col; 
		
		bool promising = true;
		for (int i = 0; i < row; ++i) {
			if (queen[i] == queen[row] || abs(queen[i] - queen[row]) == abs(i - row)) {
				promising = false;
				break;
			}
		}

		if (promising)
			dfs(row + 1);
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	
	dfs(0);
	
	cout << answer;
}

---

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기