BAEKJOON #9663) N-QUEEN (C)

알고리즘 분류: 브루트포스

9663번: N-Queen

백준 9663) N-Queen

알고리즘 분류: 브루트포스

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

int is_valid(int idx, int val, int *puzzle)
{
    int i = 0;

    while (i < idx)
    {
        if (puzzle[i] == val) {
            return (0);
        }
        if (val - puzzle[i] == idx - i || val - puzzle[i] == i - idx) {
            return (0);
        }
        i++;
    }
    return (1);
}

void solve_queens(int n, int idx, int *puzzle, int *cnt)
{
    if (idx == n) {
        *cnt = *cnt + 1;

    }
    int val = 0;
    while (val < n)
    {
        if (is_valid(idx, val, puzzle)) {
            puzzle[idx] = val;
            solve_queens(n, idx + 1, puzzle, cnt);
        }
        val++;
    }
}

int main(void)
{
    int n;
    scanf("%d", &n);
    int idx = 0;
    int cnt = 0;
    int *puzzle = (int *)malloc(sizeof(int) * n);

    solve_queens(n, idx, puzzle, &cnt);
    printf("%d", cnt);
}

• solve_queens(int n, int idx, int *puzzle, int *cnt) : 체스 판의 모든 칸들을 다 돌면서 퀸을 넣어보는 함수
• is_valid(int idx, int val, int *puzzle) : 어떤 칸에 퀸이 들어갈 수 있는지 없는지 체크하는 함수

puzzle이라는 일차원 배열의 인덱스(idx)가 column, 배열의 각 인덱스에 저장되는 값(val)을 row로 취급하여 문제를 풀었다. 

전체적으로 알고리즘을 요약하자면 0부터 N까지 인덱스(idx)를 돌면서 모든 인덱스에 0부터 N까지의 val을 넣어보면서 valid check를 한다. N개의 배열이 모두 채워지면 하나의 가능한 N-queen 체스 보드를 완성했다는 의미이므로 cnt를 하나씩 증가시킨다.

 

#예시) 5-queens에서 하나의 정답 체크 보드를 완성하는 경우를 예시로 보자.

1) idx = 0, val = 0 ✅

첫번째 시작 점은 (0, 0)부터 시작한다. 당연히 valid check를 했을 때 유효할 것이다. (사실, is_valid()함수의 반복문을 돌지 조차 않는다.) puzzle[0]에 0값이 들어가서 (0, 0)에 퀸을 넣었음을 표시하고 재귀함수를 호출하게 된다. (solve_queens(5, 1, puzzle, cnt);) idx를 1증가시켜 재귀함수를 불렀으니 다시 재귀로 들어가 val은 0부터 시작한다.

 

2) idx = 1

val = 0 → val = 1  → val = 2 ✅

solve_queens(5, 2, puzzle, cnt);

 

3) idx = 2

val = 0 → val = 1 → val = 2 → val = 3 → val = 4 ✅

solve_queens(5, 3, puzzle, cnt);

 

4) idx = 3

val = 0 → val = 1 ✅

solve_queens(5, 4, puzzle, cnt);

 

5) idx = 4

val = 0 → val = 1 → val = 2 → val = 3 ✅

solve_queens(5, 5, puzzle, cnt);
재귀로 호출된 함수에서 idx = n이 되었으므로 cnt를 증가시킨다.(체스판이 모두 채워졌다는 의미이므로)

이후에는 계속해서 그동안 쌓여있던 반복문의 스택들을 하나씩 정리해간다. 우선 idx = 4에서 while문의 val이 3까지 밖에 안돌았기 때문에 나머지 4까지 모두 돈다. → 그리고 이전에 쌓여있던 반복문 스택(?) idx=3에서의 val이 1까지 밖에 안돌았기 때문에 마저 돈다. ( ⇢ 여기서 또 valid한 위치가 나온다면 또 idx=4로 재귀가 불려져서 또 while문이 돌겠지??!?)

 

 

--------------------------------------------------------

++) C알못이 처음으로 백준 알고리즘을 C로 풀면서 표준 입력을 처음 사용해보면서 알게된 점..

표준입력 받을 때에는 인수 선언과 함께 받지 못한다!

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

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