08 The ten queens

참고 : https://chanhuiseok.github.io/posts/baek-1/
youtube : n-queens problem

0. 조건...?

보통은 N * N 체스판 위에, (4 <= N <= 15)

퀸 N개를 서로 공격할 수 없도록 놓는 경우의 수를 구하는 문제입니다.

++ 42Seoul에서는,
1. 퀸의 위치를 문자열로 나타내고,
2. 모든 방법의 총 개수를 return해야 합니다.

퀸은 같은 행, 같은 열, 대각선 /, \ 방향 모두 놓을 수 없다는 특징이 있습니다.

-> 행 마다 퀸을 하나씩 놓아 줌으로써, 특징 중 하나인 행을 고려하지 않도록 합니다.

그러면, 대각선은 어떻게 판단하죠...?

이 대각선은, x와 y를 같이 증가시키거나 감소시킨다면 찾을 수 있습니다!

\
 \
  \
   \

이 대각선은 x를 감소시키고 y값을 증가시키거나,
x를 증가시키고 y값을 감소시키면 찾을 수 있습니다!!

   /
  /
 /
/

이 때, 두 조건에는 공통점이 있어요 : )

4 * 4 맵에 만약, (2, 1)에 퀸이 놓여있다고 합시다...

그렇다면 (3, 2), (1, 0),
(1, 2), (0, 3), (3, 0) 이 대각선에 해당하는 것을 알 수 있는데,

|3 - 2| = |2 - 1|

|1 - 2| = |1 - 0|

|1 - 2| = |2 - 1|

등등등...

이 값들의 절대값, |행 번호 차이| = |열 번호 차이| 가 같다는 것을 알 수 있습니다

행 번호 차이 == 열 번호 차이 ==> 같은 대각선상!!

(초등학교, 중학교 때 배운 직선의 방정식 y = x, y = -x를 생각해봅시다.)

그리고, 문제에서 1차원 문자열로 표현해서 출력해주어야 하기 때문에,

배열을 이용해서 풉니다.

0열 (인덱스) 퀸의 위치(행). 1열 (인덱스) 퀸의 위치(행)

1행 퀸의 위치, 2행 퀸의 위치. 이렇게 이용할 수 있기 때문에, 1차원 배열로도 충분합니다.

(== 배열의 인덱스를 하나의 정보로 사용합니다!!!)

문제에서는 열로 퀸의 위치 (행) 를 표기했으므로

같은 행이 나오면 안되고, 인덱스 - 인덱스 == 행 - 행 인 값이 나오면 안됩니다!!

1142 = X !!! (행이 같은 곳에 넣어졌다!!!)
1423 = X !!! (2번째와 3번째 인덱스 차이 = 1, 2번째와 3번째 행 차이 = 1로 같아졌다!!)

그렇다면, 해당하는 조건은

if (queen[i] != queen[cnt], i - cnt != queen[i] - queen[cnt])

가 되겠다.

조건 판단

int	judge(int x, char *board)
{
	int		i;
    int		tmp;
    
    i = 0;
    while (i < x)
    {
    	tmp = board[x] - board[i];
        if (tmp < 0)
        	tmp *= -1;
    	if (board[x] == board[i] || x - i == tmp)
        	return (0);
        i++;
     }
     return (1);
}

int	nqueen(int x)
{
	int		i;
    int		cnt;
    
    cnt = 0;
    i = 0;
	if (x == 10)
    {
    	cnt++;
        print...
        return (cnt);
    }
    while (i < 10)
    {
    	board[x] = i;
        if (judge(x, board))
        	nqueen(x + 1);
        i++;
    }
    return (cnt);
}

1. 백 트래킹...

백 트래킹은, DFS를 개선한 알고리즘이라고 합니다.

DFS : 깊이 우선 탐색

모든 방법을 탐색하는 완전탐색방법이지만,

백 트래킹은 정답이 될 수 없는 것은 탐색하지 않음으로써, 탐색 효율을 높였습니다!

==> 통상 "가지치기"라고 부릅니다.

그럼 DFS가 뭔가요...?

트리나, 그래프에서 한 루트로 검색합니다. 최대한 깊숙이 들어가서 확인한 후, 없다면 다시 돌아가 다른 루트를 탐색합니다.

[재귀함수] 나 [스택]으로 구현합니다.

일전의 C 문제에서, 재귀함수를 사용해보셨을 것이라고 생각합니다.
재귀함수를 호출하고, 밑에 write, putchar 문을 두어서 최근의 것부터 출력되게 만들었잖아요!!!

비슷하다고 생각하시면 됩니다!!!

단, 여기서는 재귀함수를 실행하는데 조건을 주었습니다!

0. 방문할 그래프나, 트리, 배열등의 자료구조가 생겼습니다.

1. 먼저, 반복문을 통해, 인덱스를 변화시켰습니다.

2. 만약 해당 인덱스에 이미 접근한 상태라면, 다시 들어가지 않습니다.
   (+dfs)

3. 또 다시 조건을 주어, 해당 조건을 만족하지 않는다면 가지치기를 해주어 들어가지 않습니다!
   (+백 트래킹)

간단한 소스코드 예제

출처 : 위키백과 (dfs)
참고 : https://youtu.be/7C9RgOcvkvo

const int MAX = 100'001;

bool visited[MAX]; // 방문 배열. visited[node] = true이면 node는 방문이 끝난 상태이다.

void dfs(const vector<int> graph[], int current) { // graph는 인접 리스트, current는 현재 노드
    visited[current] = true; // current 방문

    for(int next: graph[current]) { // current의 인접 노드를 확인한다. 이 노드를 next라고 하자.
        if(!visited[next]) { // 만일 next에 방문하지 않았다면
            dfs(graph, next); // next 방문
        }
    }
}

/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   ft_ten_queens_puzzle.c                             :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: hyojeong <[email protected]>     +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2022/02/12 01:13:42 by hyojeong          #+#    #+#             */
/*   Updated: 2022/02/14 09:40:48 by hyojeong         ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include <unistd.h>

# 먼저, 해당 위치에 퀸을 놓을 수 있을지 판단하는 judge 함수
# ==> 백트래킹에 해당하겠죠!!!
int	judge(int x, int board[])
{
	int		i;
	int		tmp;

	i = 0;
	while (i < x)
	{
		tmp = board[x] - board[i];
		if (tmp < 0)
			tmp *= -1;
		if (board[x] == board[i] || x - i == tmp)
			return (0);
		i++;
	}
	return (1);
}

# 단순히 보드를 프린트해주는, 프린트 보드 함수
void	print_board(int board[])
{
	int		index;
	char	tmp;

	index = 0;
	while (index < 10)
	{
		tmp = board[index] + 48;
		write(1, &tmp, 1);
		index++;
	}
	write(1, "\n", 1);
}

# 핵심. cnt의 값을 기록해주고, 해당 위치에 퀸을 놓을 수 있다면, 다음 열로 넘어가는, 재귀를 이용한 퀸 함수!
void	queen(int x, int *cnt, int board[])
{
	int		i;

	i = 0;
	if (x == 10)
	{
		*cnt = *cnt + 1;
		print_board(board);
		return ;
	}
	while (i < 10)
	{
		board[x] = i;
		if (judge(x, board))
			queen(x + 1, cnt, board);
		i++;
	}
}

# cnt를 반환시키는, 문제에서 구현하라는 프로토타입 함수
int	ft_ten_queens_puzzle(void)
{
	int		cnt;
	int		index;
	int		board[10];

	cnt = 0;
	index = 0;
	while (index < 10)
		board[index++] = 0;
	queen(0, &cnt, board);
	return (cnt);
}

흐름

1. 먼저, board에 0000000000을 채워줍니다.

2. 퀸 재귀 함수를 실행합니다.

2-0. 왜?? (0, cnt, board)로 실행시키는 이유는 ??
해당 인덱스에 넣을 퀸을 결정하려고요!!

2-1. 퀸 재귀 함수에, board[0] = 0을 넣고, 판단합니다. 다른 곳에 퀸이 채워져 있지 않아, 당연히 통과하고 넘어갑니다.
2-2. 그리고, board의 1번째 인덱스에 채울 퀸의 위치를 결정하려고 넘어갑니다.

그런데, 해당 재귀함수는 반복문으로 실행되었고, 밑에 i++가 있잖아요??

그렇게 조건이 맞다면, 또 들어가고, 아니라면 나와서 반복문이 다시 실행되고...

이렇게 조건에 맞는 모든 퀸이 출력되고, 개수가 반환됩니다.