문제 링크: https://www.acmicpc.net/problem/9663
참고: https://st-lab.tistory.com/118

설명

퀸은 그림처럼 상하좌우 및 대각선으로 거리 제한없이 한 방향으로 이동할 수 있다.

4X4 크기의 체스판에서 퀸이 움직일 수 있는 것은 다음과 같다.

1. 첫번째 열에서 다음과 같이 놓여있다.
   

• 다음 X 표시에는 놓을 수 없고, 빈 공간에 넣어야 한다.

2. 두번째 열에서 빈 공간은 첫번째만 해당되고, 퀸이 이동할 수 있는(=공격 가능한) 경로에 모두 X 표시한다.
   

3. 세번째 열에서 빈 공간은 4번째만 해당되고, 역시 퀸이 이동할 수 있는(=공격 가능한) 경로에 모두 X 표시한다.
   

4. 네번째 열에서 빈 공간은 첫번째만 해당되고, 이동 가능한 경로를 모두 탐색했으니 탐색 가능한 경우의 수를 1 업데이트하고 종료한다.
   

위의 과정을 재귀적으로 호출하여, 이동하고 모두 배치하면 경우의 수로 더해준다.

구현해야할 것은 다음과 같다.

1. 어떻게 말을 움직이고, 재귀 호출할 것인가
2. 퀸을 놓을 수 있는 여부를 판단할 수 있는 방법은 무엇인가?

우리는 1차원 배열을 사용할 것이다.
즉 index는 퀸이 놓인 열이 되고, 원소값은 퀸이 놓인 행이 된다.

배열이 0부터 시작되는 것을 고려하여, 그림을 1차원 배열로 나타내면 [2, 0, 3, 1] 이 된다.

이렇게 첫번째열부터 하나씩 채워나가고, 놓일 수 있는 위치이면 재귀호출을 한다.

퀸을 놓을 수 있는지 아닌지는 어떻게 판단하는 것일까?

• 해당 열의 행과 i열의 행일 일치하는지 확인한다.(같은 행에 존재하는 경우)
  

• 열의 차와 행의 차가 같은지 확인한다.(대각선에 놓인 경우)
  

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n;
    static boolean[] visited;
    static int[] arr;
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());

        visited = new boolean[n];
        arr = new int[n];

        nQueen(0);
        sb.append(count);
        System.out.println(sb);
    }

    private static void nQueen(int depth) {
    	// 모든 원소를 다 채운 상태면 count를 증가하고 return한다.
        if (depth == n){
            count += 1;
        }
		
        // 시작점을 0부터 N-1까지 바꿔가면서 value를 변경한다.
        for(int i = 0; i < n; i++){
            if(visited[i]){
                continue;
            }
            arr[depth] = i;
            if(togo(depth)){
                visited[i] = true;
                nQueen(depth + 1);
                visited[i] = false;
            }
        }
    }

	// 놓을 위치가 다른 퀸으로부터 위협받는가
    private static boolean togo(int depth) {
        for(int i = 0; i < depth; i++){
        	// 해당 열의 행과 i영의 행이 일치하는 경우: 같은 행에 존재하는 경우
            if(arr[i] == arr[depth]){
                return false;
            }
            // 열의 차와 행의 차가 같으면 대각선에 놓인 경우: 대각선에 놓인 경우
            else if (Math.abs(depth-i) == Math.abs(arr[depth]-arr[i])){
                return false;
            }
        }
        return true;
    }
}

체스를 잘 몰라서 일단 어려웠다.
체스판이라서 처음에 2차원 배열로 풀었는데 인덱스의 배열이 인덱스가 있다는 점을 이용해 1차원 배열로 풀이한 것이 흥미로웠다.

추가로 알 수 있는 내용!
visited 배열을 사용하여 방문 표시를 하면, 시간을 단축할 수 있다.
+) python에서는 visited 배열이 없으면 시간 초과가 난다!
자바에서 visited 배열 없으면 5292ms나오고, visited 배열 있으면 3812ms 나온다.