[C] 백준 9663번 N-Queen : 네이버 블로그

이전에 비슷한, 어쩌면 동일하다고도 할 수 있는 문제를 풀어본 적이 있어서 쉽게 접근할 수 있었다.

퀸을 N x N 체스판에서 서로 공격할 수 없게 배치하는 경우의 수를 출력하면 된다.

먼저 떠올렸던 것은 N x N이니까, 직관적으로 2차원 배열을 0으로 초기화 시킨 후 퀸이 있는 곳을 1로 바꾸는 방법이었는데, 좀 복잡하기도 하고, 해당 문제는 오히려 1차원 배열을 통한 풀이법이 정석처럼 여겨져서 1차원으로 했다.

2차원 배열처럼 직관적이진 않지만 확실히 간단해지긴 한다. 배열의 인덱스가 세로, 즉 체스판의 행으로 보고 배열의 값을 퀸이 있는 열로 보면 된다. 예를 들어 'arr[4] = 2' 라면 퀸이 4행의 2열에 있다는 의미이다. 그러므로 malloc을 통해 입력받은 N만큼 배열 크기를 할당해주면 N x N의 정보를 모두 담을 수 있는 1차원 배열을 만들 수 있는 것이다.

문제 핵심은 백트래킹이다. 나는 아직 개념이 충분하진 않지만 해당 문제가 백트래킹의 대표적인 예제라고 한다. 내 이해를 말하자면 백트래킹은 모든 경우의 수를 탐색하여 답을 찾는 것이다. 조건에 따라 후보군을 탐색하며 유망(promising)한지 검사하고, 유망하다면 하위 깊이에서 또 탐색을 하고, 그렇지 않다면 더 하위로 가지 않고 가지치기(Pruning)를 하고 뒤로 돌아가서(Backtrack) 다음 후보군을 탐색한다. 그 과정에서 구조는 재귀를 활용하는데, 목표 깊이에 도달했을 때(배열이 다 채워졌을 때) 카운트를 ++해준 뒤 탈출조건을 설정해놓고 재귀를 돌리면 된다.

이제 서로 공격하지 못하게 배치하려면 퀸이 공격할 수 있는 루트를 생각해봐야 한다. 퀸은 가로와 세로, 대각선은 모두 움직일 수 있다. 때문에, 체스판을 2차원 배열로 보면 같은 열과 행은 당연히 위치할 수 없고, 대각선에 위치해서도 안된다.

1차원 배열에서는 인덱스 = 행 값 = 열 이기 때문에 일단 인덱스를 증가시키면서 반복문을 돌면 같은 행에는 위치할 수 없다. 그렇다면 같은 열에 있을때는 유망하지 않다는 조건을 써야하는데, 반복문을 돌면서 이전 1차원 배열에 저장되어 있는 값들과 비교하여 같은 값이 있다면 조건문을 false로 설정하면 된다.

대각선 조건은 수학적으로 조금 생각해보면 쉽게 풀린다. 정사각형 판에서 대각선의 의미는, 두 퀸을 직선으로 연결한 직선 즉, 1차원 그래프의 기울기가 1 (좌즉 대각선은 -1) 임을 의미한다. 때문에, y증가량 / x증가량 == 1, y증가량 == x증가량 이라면 대각선에 위치한다고 해석할 수 있는 것이다. 좌측 우측 모두 편하게 계산하기 위해 절대값을 씌운 후 동일한 지 조건문을 써줬다.

유망한 지 판별하는 조건

int is_Queen_valid(int nd, int i, int *arr) { 
int j = 0; 
while (j < nd) { 
	if (i == arr[j]) 
		return 0; 
	if(abs(nd - j) == abs(i - arr[j])) 
		return 0; j++; } return 1; 
}

소스코드

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

int is_Queen_valid(int nd, int i, int *arr);
int abs(int a);
void queen(int *arr, int now_depth, int final_depth, int *cnt);


int abs(int a)
{
    if (a < 0)
        return (-1 * a);
    else
        return (a);
}

int is_Queen_valid(int nd, int i, int *arr)
{
    int j = 0;
        while (j < nd)
        {
            if (i == arr[j])
                return 0;
            if(abs(nd - j) == abs(i - arr[j]))
                return 0;
            j++;
        }
    return 1;
}

void queen(int *arr, int now_depth, int final_depth, int *cnt)
{
    int i = 0;
    int size = final_depth;
    if (now_depth == final_depth)
        {
            *cnt += 1;
            return ;
        }
    
    while (i < size)
        {
            if (is_Queen_valid(now_depth, i, arr))
            {
                arr[now_depth] = i;
                queen(arr, now_depth + 1, final_depth, cnt);
            }
        i++;
        }
}

int main()
{
    int a;
    scanf("%d", &a);
    int *arr = malloc(sizeof(int) * a);
    int cnt = 0;
    queen(arr, 0, a, &cnt);
    printf("%d", cnt);
    free(arr);
}

queen에서 파라미터로 받은 함수만 잘 살펴보면 된다.

arr = 체스판을 형상화한 1차원 배열

now_depth = 현재 탐색 깊이

final_depth = 목표 탐색 깊이

cnt = 방법의 수