백준 9663 N-Queen C++ [컴공과고씨]

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

9663번: N-Queen

이 문제의 핵심은 각 행에 있을 수 있는 퀸은 단 한개라는 것을 인지하고 풀어주어야한다.

0번째 행의 퀸의 위치를 결정하고 그 다음 위치를 결정할 때 한 열씩 그 위치에 퀸이 들어갈 수 있는지 조사한 후 다음행으로 넘어가서 다시 퀸이 들어갈 수 있는 열을 구해주는 식으로 풀어주면된다. 이런 구조를 구현하려면 백트래킹 기법을 사용해야 구현이 가능하다.

 

단계별 문제풀이

1. 각 행의 퀸의 위치 열을 저장하는 배열 col 선언 

예를 들면

예시

2. 놓을 퀸의 위치를 정함하고 정한 위치의 퀸이 위쪽 퀸과 충돌하는지 확인 

충돌 조건은 같은 행에 있는지 확인, 대각선에 있는지 확인 

 

3. 충돌이 있으면 퀸의 위치를 다음 열로 넘겨주고 충돌이 없다면 다음 행으로 진행

 

4. 이렇게 진행하다 x가 입력 값 n에 도달하면 퀸을 각 행마다 놓은 것이므로 카운트 +1

 

 

백트래킹을 쓰는 이유

 

이런 식으로 다시 모든 열이 충돌한 행이 있을 때 위쪽 행으로 올라가서 다른 열의 위치로 퀸을 놓고 탐색을 진행 할 수 있기 때문에 백트래킹을 써야 한다.

 

전체코드

#include <iostream>
#include <cmath>
using namespace std;
int col[16];
int n;
int ans = 0;
void queen(int x){
    if(n == x){
        ans++; // 카운트 +1
    }else{
        for (int i = 0; i < n;i++){
            col[x] = i; // 퀸의 위치를 정함
            bool can = true;
            for (int j = 0; j < x;j++){
                if(col[x] == col[j] || abs(col[x] - col[j]) == x - j){
                    //정한 위치의 퀸이 위쪽 퀸과 충돌하는 지 확인
                    // 1. 같은 행에 있는가
                    // 2. 대각선에 있는가
                    can = false; //충돌하면 다른 열의 위치로 놓아야함
                    break;
                }
            }
            if(can){ // 충돌하지 않는다면 다음 행으로 넘어감.
                queen(x + 1);
            }     
        }
    }
} //백트래킹
 
int main(){
    cin >> n;
    queen(0);
    cout << ans;
    return 0;
} // 1.5h 

체감난이도	걸린 시간	참고	사용 알고리즘
중	힌트 보기전 (1h) 본 후 (1h) 총 2h	백트래킹 문제 유형이라는 힌트를 얻음	브루트 포스(brute force) 백트래킹(back tracking)

 

yea!