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

3월 29일(수) - 백트랙킹 (9663번)

9663번: N-Queen

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 백트랙킹 문제들을 전체적으로 복습하다보니, 골드4 문제지만 풀 수 있을 것 같아서 도전

- N x N인 체스판에 N개의 퀸이 서로를 공격할 수 없게 놓는 경우의 수를 최종적으로 구해야하는 문제이다

- 따라서 백트랙킹의 기본구조에서 if( == ) 부분은 변수 row가 변수 N과 같아진 경우,

  즉 특정 위치에 퀸을 놓은 상황에서, 모든 행의 경우를 고려하여 최종적인 경우의 수를 +1 할 수 있을때로 잡았다

- 백트랙킹의 기본구조에서 else 부분은 행 값이 N보다는 작지만, 행 값이 하나 추가된 상황에서,

  해당 행의 모든 열을 하나하나 반복문으로 돌며 퀸을 놓을 수 있는 자리인지를 검사하는 과정으로 잡는다

- 또한 특정 열에 퀸을 놓을 수 있다고 판단한 경우에 한정해서만 재귀를 통해서 함수를 다시 부른다

  여기서 퀸을 놓을 수 있는 자리인지를 판단하는 함수를 추가적으로 만들어야겠다고 생각

- 현재 행을 하나잡고, 거기서 다시 하나하나의 열의 위치를 검사하고있으므로 퀸이 가로로 동일하게 놓일 수는 없다

  따라서 퀸이 세로로 같은 선상에 놓이는 경우 / 대각선으로 같은 선상에 놓이는 경우

  이렇게 2가지 경우에 해당하는지를 함수를 통해 검사해야한다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. 퀸을 놓을 수 있는지를 판단하는 함수를 만들다보니, 기존에 2차원 배열로 만들었던 board[15][15]가 불편함

-> 1차원배열 board[15]로 수정

-> 그리고 i행 j열의 값을 board[ i ] = j 로 나타내는 것으로 수정

 

2. 퀸을 놓을 수 있는 자리인지를 판단하는 함수는 2가지를 고려해야한다

1) 퀸이 세로로 같은 선상에 놓이는 경우 ->  다른 행이지만 열의 값이 같은 것 이므로 board[ ] 값이 같은지로 판단

2) 대각선으로 같은 선상에 놓이는 경우

-> 어떤 조건으로 판단해야할지 고민

-> 결국 대각선으로 같은 선상에 위치하려면 2개의 퀸이 정사각형의 서로 반대쪽 꼭짓점을 이루어야한다

-> 따라서 2개의 퀸이 만드는 작은 정사각형의 세로와 가로 길이가 같은지로 판단해야한다

-> 이때 세로길이는 row값의 차이로, 가로길이는 board[ ]값의 차이로 계산한다

 

3. 위의 과정에서 세로길이는 대소관계를 알고있지만, 가로길이는 대소관계가 불분명해서 절댓값을 활용해야한다

-> stdlib.h에서 abs를 활용할 수 있다는 것을 까먹고, 절댓값을 출력하는 함수를 추가적으로 만드려다가 지웠다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

int N;
int count = 0;
int board[15];

int live_or_die(int row)
{
	for (int i = 0; i < row; i++)
	{
		if (board[i] == board[row] || row - i == abs(board[row] - board[i]))
		{
			return 0;
		}
	}
	return 1;
}

void nqueen(int row)
{
	if (row == N)
	{
		count++;
		return;
	}

	else
	{
		for (int i = 0; i < N; i++)
		{
			board[row] = i;
			if (live_or_die(row) == 1)
			{
				nqueen(row + 1);
			}
		}
	}
}

int main(void)
{
	scanf("%d", &N);
	nqueen(0);
	printf("%d", count);

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ