백트래킹 - 백준9663 N-Queen

하루종일 풀어봐도 답이 안나와서 해답을 본 후 차이를 중심으로 오답노트를 작성해 보겠다.

나의 시도
1. 재귀로 탐색하는 범위 : 2차원배열을 돌면서 퀸 N개를 다 놓았을 때 return
2. 대각선을 검사하는 방법 : 현재 row, col을 기준으로 좌측상단을 구하고, 우측상단을 구하고, 좌측상단부터 우측하단까지, 우측상단부터 좌측하단까지 탐색하며 검사

import java.io.*;
import java.util.*;
public class Main{
    static int n;
    static int[][] arr;
    static int answer = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //N x N 체스판, 퀸 N 개, 서로 공격 못함
        // -> 경우의 수
        //브루트포스 -> 백트래킹
        //각 단계마다 검증후 하나놓고, 그다음 놓고 반복
        //0,0부터 n-1,n-1까지, 0부터 n이면 return
        //검증 시 더 놓을 자리가 없는 경우(continue)
        //N개를 다 놓은 경우(return)
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        go(0);
        System.out.println(answer);
    }
    static void go(int nowN){
        if(nowN == n){
            //n개를 다 놓았으면
            answer++;
            return;
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                //체스말 놓기전에 검사
                if(cantPut(i, j)){
                    //못놓는 자리면
                    continue;
                }
                //체스말 놓기
                arr[i][j] = 1;
                go(nowN+1);
                //체스말 덜어내기
                arr[i][j] = 0;
            }
        }
    }
    static boolean cantPut(int row, int col){
        //arr을 탐색하며 각 퀸을 찾기
        //해당 퀸의 공격범위 검사
        //공격범위 해당 시 break 후 continue
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(arr[i][j] == 1){
                    //각 퀸을 찾고, 그 퀸과 행이 같거나 열이 같으면 true
                    if(i == row || j == col){
                        return true;
                    }
                    //대각선 검사
                    //좌상, 우상 찾기 각각 최하단까지 내려오는데 
                    //그 위치와 row,col과 같은지
                    int rowPoint = i;
                    int colPoint = j;  
                    //좌상 찾기
                    while(rowPoint > 0 || colPoint > 0){
                        rowPoint--;
                        colPoint--;
                    }
                    //최하단까지 내려가기
                    while(rowPoint < n || colPoint < n){
                        if(rowPoint == row && colPoint == col){
                            return true;
                        }
                        rowPoint++;
                        colPoint++;
                    }
                    rowPoint = i;
                    colPoint = j;  
                    //우상 찾기
                    while(rowPoint > 0 || colPoint < n-1){
                        rowPoint--;
                        colPoint++;
                    }
                    //최하단까지 내려가기
                    while(rowPoint < n || colPoint >= 0){
                        if(rowPoint == row && colPoint == col){
                            return true;
                        }
                        rowPoint++;
                        colPoint--;
                    }
                }
            }
        }
        return false;
    }
}

시간초과에 답도 틀림

해답에 따른 풀이
1. 재귀로 탐색하는 범위 : 어차피 한 행에는 1개만 놓을 수 있으므로, 0번째 행부터 N번째 행까지 놓은 후 return
2. 대각선을 검사하는 방법 : / 대각선인 경우 : 각각 x + y가 같은지,
\ 대각선인 경우 : 각각 x - y가 같은지 비교하여 검사

import java.io.*;
import java.util.*;
public class Main{
    static int n;
    static int answer;
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        go(0);
        System.out.println(answer);
    }
    static void go(int nowRow){
        if(nowRow == n){
            //N번째 열까지 못채워질 수도 있는거잖아 그럴리는 없다 N개를 N번째 행까지 놓으므로
            answer++;
            return;
        }
        for(int i = 0; i < n; i++){
            //현재 열(nowRow, i)이 놓을 수 있는 열인지 검사
            //or continue
            int RCheck = nowRow + i;
            int LCheck = nowRow - i;
            boolean impossible = false;
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(arr[j][k] == 1){
                        if(nowRow == j || i == k || (j+k == RCheck) || (j-k == LCheck)){
                            impossible = true;
                            break;
                        }
                    }
                }
                if(impossible){
                    break;
                }
            }
            if(impossible){
                continue;
            }
            arr[nowRow][i] = 1;
            go(nowRow+1);
            arr[nowRow][i] = 0;
        }
    }
}

차이점 두 가지 모두 시간복잡도에 큰 영향을 미치므로 아래 풀이가 해답