백준 9663 C++

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

퀸이 서로 공격할 수 없게 놓는 방법 : 같은 행 / 같은 열 / 같은 대각선 상에 위치하지 않아야 한다.

 

(최지웅 교수님한테 배운 ㅎ) 생각
1. 백트래킹 문제니까 되추적 알고리즘을 쓴다
 1.1. 상태 조건 트리를 어떻게 구성할 것인가? -> 트리까지 그릴 필요는 없는 문제인듯 아닌가 하하
 1.2. promising 조건을 뭘로 할 것인가? -> 행 / 열 / 대각선이 겹치는지 확인하기

 

1차원 배열을 써도 되는 이유

그림을 그려보자... ㅜㅜ

#include <iostream>
using namespace std;

int N, cnt=0;
int col[15];

void queens(int i);
bool promising(int i);

int main()
{
    cin >> N;
    queens(0); // queens(N)이라는 멍청한 짓 하지 말기....................
    cout << cnt;
}

void queens(int i)
{
        if (i == N)
        {
            cnt++;
        }
            for (int j = 0; j < N; j++)
            {
                col[i] = j; // col[0] = 0 / 1 / 2 / 3 ... 을 promising에서 k와 비교
                
                if(promising(i)){ // 유망하면(true) / 유망하지 않으면(false)
                    queens(i + 1);
                }
            }
}

bool promising(int i)
{
    for(int k=0 ; k<i ; k++){
        if (col[i] == col[k] || abs(col[i] - col[k]) == abs(i - k))
        {
            return false;
        }
    }
    return true;
}