[JAVA] SWEA 2806 - N-Queen

N개의 퀸을 서로 공격하지 못하게 놓으려면 결국 각 행마다 하나의 퀸만 존재해야 하기 때문에 재귀함수 호출로 각 행마다 퀸의 위치를 정하는식으로 짜면 된다.

시간복잡도는 O(N^3)정도가 나올 것 같다. 문제에서 N의 크기가 최대 10이기 때문에 시간초과가 나오진 않는다.

import java.util.*;

class Location{
    int y;
    int x;
    Location(int y, int x){
        this.y = y;
        this.x = x;
    }
}
class Solution
{
    static int count = 0;

	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);

        StringBuffer sb = new StringBuffer();

        int T = sc.nextInt();

        for(int tc=1; tc<=T; tc++){
            sb.append("#").append(tc).append(" ");
            
            int N = sc.nextInt();
            count = 0;
            solve(0, N, new ArrayList<>());
            sb.append(count).append("\n");
        }
        System.out.println(sb);
	}
    static void solve(int c, int N, List<Location> list){
        if(c >= N){
            count++;
        }
        for(int i=0; i<N; i++){
            boolean isPossible  =  true;
            for(int j=0; j<list.size(); j++){
                Location loc = list.get(j);
                //열이 겹칠 수 있는지 확인
                
                if(i == loc.x){
                    //열이 겹침
                    isPossible = false;
                    break;
                }
                //대각선에 있는지 확인
                {
                    int rd = Math.max(loc.y, c) - Math.min(loc.y, c);
                    int cd = Math.max(loc.x, i) - Math.min(loc.x, i);

                    if(rd == cd){
                        //대각선에 있음
                        isPossible = false;
                        break;
                    }
                }
            }
            if(isPossible){
                Location loc = new Location(c,i);
                list.add(loc);
                solve(c+1, N, list);
                list.remove(loc);
            }
        }

    }
}