[추석맞이 코딩챌린지 Bonus] 공격할 수 없는 Queen c

문제 출처 : https://cafe.naver.com/codeuniv?iframe_url=/ArticleList.nhn%3Fsearch.clubid=30026525%26search.menuid=193%26search.boardtype=L 

코딩 커뮤니티 - 코뮤니티 [파이썬/... : 네이버 카페

문제

체스에서 퀸은 상하좌우는 물론, 대각선으로도 이동할 수 있는 기물이다.

8 퀸 문제는 8x8 크기의 체스판에 퀸을 서로 공격할 수 없도록 8개 배치하는 문제로, 1848년 막스 베첼이 처음 고안 해 내었다.

​

이를 일반화 하여 N x N 크기의 체스판이 있을 때, N개의 퀸이 서로 공격 할 수 없는 경우의 수를 출력하세요.

 

입/출력 예시

👉 입력 예시

8

👉 출력 예시

92

​

👉 입력 예시

12

👉 출력 예시

14200

 

풀이

2021.09.02 - [알고리즘 문제 풀이/백준] - 백준 9663 N-Queen Kotlin,c (백트래킹)

위의 문제와 같은 문제다!

해당 문제는 가로, 세로, 대각선으로 공격할 수 있는 퀸들을 서로 공격하지 못하게 두는 문제로,

dfs로 퀸을 놓을 수 있는 자리는 모두 탐색하되,

퀸이 서로 공격할 수 있는 자리는 탐색하지 않아서 불필요한 탐색을 가지치기로 줄이는 전형적인 백트래킹 문제이다.

 

체스판은 1차원 배열로 구현이 가능하며, graph[row] = i는 '체스판의 row행에 i열에 퀸을 놓았다.'라는 의미이다.

0행부터, 현재 행의 i열에 퀸을 놓고, 이전 행들을 검사하여 현재 행의 i열에 퀸을 놔도 되는지 검사한다.

만약 퀸을 놓을 수 있다면 다음 행의 0~n-1열을 검사하고, 이를 n-1행까지 재귀로 반복한다.

row가 n에 다다르면, 0행부터 n-1행까지 n 개의 퀸을 모두 놓았으므로 answer++하고 return한다.

 

코드

#include <stdlib.h>
#include <stdio.h>

int answer = 0;
bool check(int *graph, int row) {
	for (int i = row-1; i >= 0; i--) {
		//위의 행들이 세로로 있거나 대각에 있으면 return false
		if (graph[i] == graph[row]) {
			return false;
		}
		if (abs(graph[row] - graph[i]) == abs(row - i)) {
			return false;
		}
	}
	return true;
}


void backTracking(int *graph,int row, int n) {

	if (row == n) {
		answer++;
		return;
	}
	
	//체스판의 각 행마다 모두 퀸을 놓아보고, 되면 다음 행, 안 되면 다음 열
	for (int col = 0; col < n; col++) {
		graph[row] = col;
		if (check(graph, row)) {
			backTracking(graph, row + 1, n);
		}
		graph[row] = 0;
	}
	
}

int main() {

	int n;
	scanf("%d", &n);

	//동적 배열
	int *graph = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++) {
		graph[i] = 0;
	}
	backTracking(graph,0, n);
	printf("%d", answer);
	return 0;
}