백준 9663 N-Queen

문제링크 : https://www.acmicpc.net/problem/9663

아이디어

• 퀸이 놓는 위치를 백트래킹 하자
• 그냥 할 경우 시간복잡도가 어마어마하게 큼
  • O(N^2^(N^2)) : 225^225
  • 그래서 가지를 쳐가면서 백트래킹 시작
• 퀸이기 때문에 한번에 한줄씩 밖에 안들어감
  • 한줄씩 백트래킹 수행
  • 세로의 경우 추후 별도 배열 만들어서 중복체크 해주자

시간복잡도 계산

• 한줄에 하나씩 들어가는 백트래킹이므로
  • O(N^N) = 15^15
  • 시간초과 날것 같지만
  • 중간 중간 가지를 칠 것으로 예상하며 해보자

자료구조

• bool column[15] : 해당 컬럼에 퀸 있는지 체크
• 경우의 수 : cnt
  • 최대 15^15 될수도 있으므로, 혹시 모르니 long long으로 사용
• 전체 맵 bool map[15][15]

코드(C++)

#include <iostream>
 
using namespace std;
typedef long long ll;
 
bool map[20][20];
bool column[20];
 
int N;
ll cnt;
 
bool diagonalChk(int y, int x) {
    // 왼쪽 대각선
    int j = y;
    int i = x;
    while(j>=0 && i >=0) {
        if(map[j][i]) return 1;
        j--;
        i--;
    }
    
    // 오른쪽 대각선
    j = y;
    i = x;
    while(j>=0 && i < N) {
        if(map[j][i]) return 1;
        j--;
        i++;
    }
    
    return 0;
    
}
void dfs(int y) {
    if(y==N) {
        // N개를 놓는 경우 cnt 증가
        cnt++;
        return;
    }
    
    for(int i=0; i<N; i++) {
        if(column[i]) continue;
        if(diagonalChk(y,i) == true) continue;
        column[i] = 1;
        map[y][i] = 1;
        
        dfs(y+1);
        
        column[i] = 0;
        map[y][i] = 0;
    }
    
}
 
int main() {
    // 초기화
    fill(column, column+20, 0);
    fill(&map[0][0], &map[19][20], 0);
    cnt=0;
    
    cin >> N;
    
    dfs(0);
    
    cout << cnt << '\n';
    
    return 0;
}
 

문제유형

• 백트래킹 - 2차원 경우의수

비슷한 문제

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