[백준] 9663번 : N-Queen [C/C++]

#문제

9663번: N-Queen

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

9663번: N-Queen

 

---

#접근방법

모든 경우의 수를 구하는 백트래킹 기법으로 접근하면 된다.

반응형

---

#풀이

#include <stdio.h>

int n,ans;
int	col[15],updia[29],downdia[29];

void NQueen(int x){
	for(int i=0;i<n;i++){
		int up = x+i;
		int down = n+x-i-1;
		
		if(!col[i] && !updia[up] && !downdia[down]){
			if(x==n-1){
				ans++;
				continue;
			}
			
			col[i] = updia[up] = downdia[down] = 1;
			NQueen(x+1);
			col[i] = updia[up] = downdia[down] = 0;
		}
	}
	
	return;
}

int main(){
	scanf("%d",&n);
	
	NQueen(0);
	
	printf("%d",ans);
	
	return 0;
}

 

N이 15까지 주어져서 모든 경우의 수를 구해도 시간안에 돌아간다.

 

NxN크기의 체스판위에 퀸 N개를 서로 공격할 수 없도록 놓아야 한다.

 

퀸은 가로, 세로, 대각선 전체가 공격 범위이다. 따라서 퀸을 어떤 칸에 놓을 때, 다른 퀸의 공격범위에 들어가지 않도록 체크를 해주어야 한다. col배열은 세로줄, updia배열은 위로 향하는 대각선줄, downdia배열은 아래로 향하는 대각선줄로 체크를 해준다. 가로줄은 0 ~ n-1까지 반복문을 돌리면서 한 칸씩 퀸을 놓을 수 있는지 체크하므로 가로줄을 체크할 배열은 필요가 없다.

 

해당 칸에 col[i], updia[up], downdia[down]이 0이면 퀸을 놓을 수 있다는 뜻이므로 1로 체크를 해주고 NQueen(x+1)으로 다음줄로 이동시켜준다.

 

마지막 줄에서 해당 칸에 col[i], updia[up], downdia[down]이 0이면 N개의 퀸을 놓았다는 뜻이므로 ans++를 하고 continue;로 다음 칸을 체크해준다.

 

ans를 출력하면 정답이다.

---

#성능

---

#정리

모든 경우의 수를 구해야 한다는 것을 알고 백트래킹으로 접근을 하는 것,

 

가로, 세로, 양쪽 대각선을 체크해주는 배열을 사용함으로써 O(1)의 시간복잡도로 퀸을 해당칸에 놓을 수 있는지 확인을 할 수 있다면 풀 수 있는 문제였다.