[백준 풀이] 백준 9663 "N-Queen"

https://www.acmicpc.net/problem/9663
직접 공책에 써보면 이해가 좀 더 쉬운것 같습니다.
전체적인 흐름은 다음 그림과 같습니다.(글씨체가 너무 안좋아서 그림만 보시면 될것 같습니다)

위 그림은 N=4로 예를 들었습니다.
먼저 기본적으로 시작은 첫번째 줄의 왼쪽부터 오른쪽까지 반복하며 경우의 수를 찾습니다. 그 후 재귀호출을 통해서 두번 째줄과 세번째 줄 N번 째 줄까지 탐색하며 해결책이 없으면 다시 뒤로 백트래킹합니다.

이제 Feasible 함수에 대해 간단하게 알아보면 이 함수는 해당 위치에 퀸을 놓을 수 있는지 여부를 알려줍니다.
이 때 가로 인덱스의 값을 비교해서 같으면 가로, 세로에 퀸이 있는것이고 가로의 차와 세로의 차를 비교해서 같으면 대각선에 퀸이 이미 놓여져있는겁니다. 그리고 이 두 연산을 or 연산해서 최종적으로 true인지 false인지 구합니다.

여러가지 시행착오가 있었는데 제가 겪은 시행착오는 자꾸 모든 판을 하나씩 돌아다니면서 4*4면 16칸을 모두 돌아가면서 경우를 알아봐야한다고 생각했는데 직접 그려보면서 제일 첫째 줄만 돌아다니면서 밑에줄로 가고 해결책이 없으면 백트래킹하는 형태로 알고리즘을 짜야한다는것을 알았습니다.

다음은 제가 작성한 자바 코드입니다.

import java.util.Scanner;
import java.lang.Math;

public class Main {
    static int count = 0;
    static int[] already;
    static boolean Feasible(int idx) {
        for(int i = 0;i < idx;i++) {
            if(already[idx] == already[i] || idx - i == Math.abs(already[idx] - already[i])) {
                return false;
            }
        }
        return true;
    }
    static void Nqueen(int N, int idx) {
        if(idx == N) {
            count++;
            return;
        }
        for(int i = 0;i < N;i++) {
            already[idx] = i;
            if (Feasible(idx)) {
                Nqueen(N, idx + 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        already = new int[N];
        Nqueen(N, 0);
        System.out.print(count);
    }
}

다음에는 스도쿠까지 풀어서 백트래킹 개념을 어느정도 정리해야겠습니다.