[백준][9663] N-Queen

[9663] N-Queen

Algorithm: 백트래킹 Created: Jan 28, 2020 5:29 PM DoubleChk: No Type: 백준 link: https://www.acmicpc.net/problem/9663

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

8

예제 출력 1

92

---

    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <string.h>
    using namespace std;
    int n, ans;
    int chess[16][16];
    bool check(int row, int col){
    
        //세로
        for(int i=0; i<row; i++){
            if(chess[i][col] == 1) return false;
        }
    
        //대각선
    
        int check_right = col + 1;
        int check_left = col - 1;
    
        for (int i = row - 1; i >= 0; --i)
        {
            //check '/' diag
            if (check_right < n && chess[i][check_right] == 1)
                return false;
            else
                check_right++;
    
            //check '\' diag
            if (check_left > -1 && chess[i][check_left] == 1)
                return false;
            else
                check_left--;
        }
    
        return true;
    }
    void solve(int num){
        if(num == n){
            ans++;
            return;
        }
    
        for(int i=0; i<n; i++){
            if(check(num, i)){
                chess[num][i] = 1;
                solve(num+1);
                chess[num][i] = 0;
            }
        }
    
    }
    int main(){
    
        cin >> n;
        solve(0);
        cout << ans << endl;
    }

• 문제 풀이

  퀸은 가로, 세로, 대각선을 모두 공격할 수 있다.

  따라서 한 줄에 퀸을 하나 씩 놓을 때 마다, 그 줄에 놓을 수 있는 퀸을 다 놓은 것이다.

  그래서 반복문을 돌면서, 한 줄에 하나씩 퀸을 놓아 본다.

  퀸을 놓을 때 마다, 가로, 세로, 대각선에 다른 퀸이 있는지 체크 한다!

  이것을 반복하다가 퀸을 다 놓으면 답을 더한다.

• 후기

  처음 이문제 접했을때는 진짜 암것도 모르겠었는데 이제는 아는거 보니 성장했다 눈물난다