[DFS] 9663번 N-Queen

9663번 N-Queen

 

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

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

8

 

예제 출력

92

 

해결방법

체스룰

• Queen은 위, 아래, 대각선 모두 이동 가능함

 

백트래킹을 하면서 DFS 탐색을 하는 문제이다.

이 문제는 NxN 체스판에 N개의 퀸을 둬야하는데 각 Row마다 하나의 퀸이 존재해야한다는 개념을 이해하여야 문제에 접근할 수 있다. 그렇다면 정답을 찾은 경우는 'row == N' 이 될 것이다.

DFS 구현 부분에서 어짜피 다음 퀸은 다음 행이기 때문에 2중 for문 대신 1중 for문으로 구현을 할 수 있다. (처음에는 2중 for문으로 구현을 하였지만 시간초과가 나왔다)

또한 양쪽 위 대각선과 위쪽에 퀸이 있나 확인하는 is_possible() 함수를 구현해야 했다.

이 구현부는 사실 감이 잡히지 않아 인터넷 검색을 활용하였다.

bool is_possible(int row,int col){
    // 위 검사
    int x = row-1; int y = col;
    while(x>=0){
        if(map[x][y]) return false;
        x--;
    }
    // 왼쪽 위 대각선 검사
    x = row-1; y = col-1;
    while(x>=0 && y>=0){
        if(map[x][y]) return false;
        x--;
        y--;
    }
    // 오른쪽 위 대각선 검사
    x = row-1; y = col+1;
    while(x>=0 && y<n){
        if(map[x][y]) return false;
        x--;
        y++;
    }
    return true;
}

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 15
#define INF 987654321
using namespace std;

int n;
int ans;
bool map[MAX][MAX];

bool is_possible(int row,int col){
    // 위 검사
    int x = row-1; int y = col;
    while(x>=0){
        if(map[x][y]) return false;
        x--;
    }
    // 왼쪽 위 대각선 검사
    x = row-1; y = col-1;
    while(x>=0 && y>=0){
        if(map[x][y]) return false;
        x--;
        y--;
    }
    // 오른쪽 위 대각선 검사
    x = row-1; y = col+1;
    while(x>=0 && y<n){
        if(map[x][y]) return false;
        x--;
        y++;
    }
    return true;
}

void dfs(int row){
    if(row == n){
        ans++;
        return;
    }
    
    // DFS
    for(int col=0; col<n; col++){
        if(!map[row][col] && is_possible(row,col)){
            map[row][col] = true;
            dfs(row+1);
            map[row][col] = false;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    // 초기화
    for(int i=0; i<n; i++){
        memset(map[i], false, sizeof(map[i]));
    }
    ans = 0;
    dfs(0);
    cout << ans << endl;
}