SWEA 2806 N-Queen

import java.util.Scanner;

public class N_queen {
    static int N;
    static int[][] map;
    static int answer = 0;
    public static void main(String args[]) throws Exception
    {

        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = sc.nextInt();
            answer = 0;
            map = new int[N][N];
            dfs(0,0);
            System.out.println(answer);
        }
    }
    public static void dfs(int row,int count){

        if(count==N){
            answer++;
            return;
        }
        for (int i = row; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(check(i,j)){
                    map[i][j] = 1;
                    dfs(i+1,count+1);
                    map[i][j] = 0;
                }
            }
        }

    }
    public static boolean check(int row, int col){
        boolean flag = false;
        for (int i = 0; i < N; i++) {//가로
            if(map[row][i]!=0)flag = true;
        }
        for (int i = 0; i < N; i++) {//세로
            if(map[i][col]!=0) flag = true;
        }
        for (int i = 0; i < N; i++) {//대각선 4방향
            if(row+i<N&&col+i<N){
                if(map[row+i][col+i]!=0) flag = true;
            }
            if(row-i>=0&&col+i<N){
                if(map[row-i][col+i]!=0) flag = true;
            }
            if(row+i<N&&col-i>=0){
                if(map[row+i][col-i]!=0) flag = true;
            }
            if(row-i>=0&&col-i>=0){
                if(map[row-i][col-i]!=0) flag = true;
            }
        }
        if(!flag){
            return true;
        }
        return false;
    }
}

풀이방법

1. map을 완전탐색으로 0,0부터 check 함수로 가로,세로, 대각선 4방향을 확인하고(범위설정 주의) 놓을 수 있다면 퀸을 자리에 놓는다. (map[i][j] = 1;)
2. 자리에 놓았다면 다음 행으로 넘어가서 다시 탐색을 시작한다.
3. 퀸 8개를 놓았다면 answer을 증가시키고 끝낸다.
4. 퀸 8개를 놓을수 없는 경우의 수 라면, 하나씩 다시 되돌아가며(백트래킹) 퀸을 지우고 다른 좌표에 다시놓으며 탐색한다.

후기

백트래킹의 기본 구조인데, 빡빡한 시간제한과, 체크로직, 배려없는 테케(0,1 줄꺼면 걍 주지말던가 뭐하는거)때매 헷갈릴만한 문제이다.