[BOJ] 9663 : N-Queen

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
//BOJ :: 9663 N-Queen
//2019-03-05
public class Main9663_NQueen {
    static int[][] map;
    static int n, ans;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(bf.readLine());
        ans = 0;
 
        // 1행에서 퀸의 위치를 정해준다.
        for (int j = 0; j < n; j++) {
            map = new int[n][n];
            solve(0, j, 1);
        }
        System.out.println(ans);
    }
 
    static int[] dx = { -1, 0, 1, 0, 1, -1, 1, -1 };
    static int[] dy = { 0, 1, 0, -1, -1, -1, 1, 1 };
 
    public static void solve(int y, int x, int q) {
 
        map[y][x]++; // visited
        
        //(y,x) 좌표에 퀸을 놓고 다른 퀸을 놓을수 없는 곳에 visit check 를 한다.
        //퀸의 위치를 중심으로 8방향에 대하여 배열의  범위를 초과하는 지점까지 while문을 반복한다.
        for (int i = 0; i < 8; i++) {
            int ny = y, nx = x;
            while (true) {
                ny += dy[i];
                nx += dx[i];
 
                if (ny < 0 || ny > n - 1 || nx < 0 || nx > n - 1)
                    break;
                map[ny][nx]++;
            }
        }
 
        if (q == n) {// 종료조건 : n개의 퀸을 놓으면 재귀함수를 종료한다.
            ans++;
            return;
        }
        
        //다음행인 (y+1)행에 퀸을 놓을 수 있는 곳을 탐색한다.
        for (int k = 0; k < n; k++) {
            if (map[y + 1][k] > 0)
                continue; // 방문한 곳은 continue;
 
            solve(y + 1, k, q + 1);
            
            
            //Backtracking
            //놓았던 퀸을 회수하고,
            map[y + 1][k]--;
            //해당 퀸에 의해 visit 체크 되었던 곳을 해제한다.
            for (int i = 0; i < 8; i++) {
                int ny = y + 1, nx = k;
                while (true) {
                    ny += dy[i];
                    nx += dx[i];
 
                    if (ny < 0 || ny > n - 1 || nx < 0 || nx > n - 1)
                        break;
                    map[ny][nx]--;
                }
            }
 
        }
 
    }
}
 

**** visit 체크를 boolean 타입이 아닌 cnt++ 로 해주는 이유

여러 퀸을 놓으면서 해당 퀸에 의해서 8방향으로 visit 체크 되는곳이 겹치는 경우가 발생합니다.

만약, 재귀 함수가 끝나고 퀸을 회수하면서 visit 체크를 해제할때 boolean 타입으로 true를 false로 바꿔준다면

다른 퀸에 대해 visit 체크 되었던 곳임에도 불구하고 visit이 해제 될 수 있습니다.

int 형으로 카운트 해주며 visit을 체크하면 그런 상황을 방지할 수 있읍니당 ,,