백준 9663번 N-Queen

 

 

문제 보러가기 : https://www.acmicpc.net/problem/9663

 

 

9663번: N-Queen

 

 

 

이번 문제는 전형적인 백트래킹(BackTracking) 문제였습니다.

 

2차원 배열을 직접 선언하지 않고 1차원 배열을 선언하여

배열의 인덱스는 행을 나타내고 배열에 저장된 값은 열을 나타내도록 해주었습니다. 

 

 

 

 

《문제 풀이》

 

1. 퀸을 놓을 위치를 찾기 위해 dfs 수행 --> queen(0) 부터 시작

2. 퀸을 놓을 위치가 유망한 위치인지 검사하기 위한 함수 possible

     (1) chess[1] 부터 비교하면서 반복문 돌 때마다 prev++  

     (2) 전에 퀸을 놓았던 위치와 같은 열이거나 대각선이라면  flag = false

3. 유망한 위치라면 

     (1) 체스판에 N개의 퀸을 모두 놓았다면 cnt++

     (2) 그렇지 않다면 다음 행을 기준으로 dfs 수행 

 

 

 

 

《C++ 코드》

 

#include <iostream>

using namespace std;

int N;
int cnt = 0;
int chess[16];

bool possible(int cur) {
	int prev = 1; // 이전 행  
	bool flag = true;
	
	while(prev < cur && flag) {
		// 같은 열이거나 대각선이면  
		if(chess[cur]==chess[prev] || abs(chess[cur]-chess[prev]) == cur-prev)
			flag = false;
		prev++;
	}
	return flag;
}

void queen(int row) {
	if(possible(row)) {
		if(row == N) // 체스판에 N개의 퀸을 놓았다면   
			cnt++;
		else {
			for(int i=1; i<=N; i++) {
				chess[row + 1] = i;
				queen(row + 1);
			}
		}
	} 
}

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

	cin>>N;
	queen(0);
	cout<<cnt;
	
	return 0;
}

 

 

개발 환경: Dev-C++ 

 

 

baekjoon - 정답 화면