[C++/BOJ] 9663 : N-Queen (완전탐색, Backtracking)

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

문제

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

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

입력

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

출력

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

---

 

 

문제 힌트에 퀸의 Show must go on 노래가 있길래 신나게 들으면서 풀었음

 

백준 티어 골드4, 완전탐색 + 백트래킹 문제이다.

 

처음에 백트래킹 알고리즘으로 풀긴 풀었지만 재귀 과정이 잘 이해가 안되었는데,

어떤 동영상의 아래 그림을 보고 바로 이해가 되었다.

재귀의 흐름과 끊김을 바로 볼 수 있는 그림이다!

 

출처 : https://www.youtube.com/watch?v=ltm-JX5R1pA&ab_channel=%EC%BD%94%EB%94%A9%EB%9E%A9CodingLab

 

main ideas

 

1. 어차피 matrix로 두어도 같은 행과 열에는 퀸을 못 두므로 이차원배열이 아니라 일차원 배열로 풀 수 있다. 

 

2. 퀸이 있는 곳과 같은 행, 같은 열, 대각선에는 다른 퀸을 놓지 못한다.

따라서 일차원 배열의 i 번째 열에 퀸을 놓고, 열이 겹치거나 대각선에 있다면 중지한다. (backtracking)

이때, 대각선 확인은 (x,y) (x+1,y+1) 이 대각선(기울기가 1)임을 이용한다. (x끼리의 차 == y끼리의 차)

 

3. canGo() 에서 true가 반환되면, 그 다음 행으로 이동한다.

놓은 퀸의 갯수가 n개가 되면 answer을 1만큼 증가시킨다.

 

 

 

나의 풀이

#include <iostream>
using namespace std;

int n;
int line[15] = {0};
int answer = 0;

bool canGo(int x){
    for (int i = 0; i < x; ++i){
        if(line[x] == line[i]) return false; // y값이 같다?(같은 열이다?) false
        if(abs(line[x]-line[i]) == x-i) return false; // 대각선 라인이다? false
    }
    return true;
}

void queen(int x){
    if(x==n) {
        answer++;
    }
    else{
        for (int i = 0; i < n; ++i){
            line[x] = i; // x행의 i번째 열에 퀸 놓기
            if(canGo(x)) queen(x + 1);
        }
    }
}

int main(){
    cin >> n;
    queen(0);
    cout << answer;
    return 0;
}