[백준 9663] N-Queen (Java)

https://www.acmicpc.net/problem/9663

 

접근 방법

1차원 배열을 만들어 행은 인덱스에 열은 해당 행의 번째에 배열의 값으로 들어가게 하였다.

(예를 들어, 1행 3열이면 positoins[1] = 3)

 

백트래킹 알고리즘을 통해 1 -> N행으로 depth를 넘어가면서 조건을 통과하는 경우 다음 깊이로 재귀하도록 구현했다.

 

다음 깊이로 재귀하는 조건과 구현 방법은 다음과 같다

1. 이미 같은 열에 퀸이 놓여있지 않은 경우

-> 열을 나타내는 것은 1차 배열의 값이다. 따라서 이전까지의 배열 인덱스를 탐색하면서 값이 존재하지 않으면 조건에 부합하다. 즉, position[i] != number

 

2. 이미 놓여있는 퀸이 대각선에 있지 않은 경우

-> 대각선에 놓여있는 경우의 기울기는 |1|임을 이용한다. |y2 - y1 / x2 - x1| = 1이기 때문에 |y2 - y1| != |x2 - x1|인 경우 조건에 부합하다.

 

재귀 함수의 끝은 depth == N, 다시 말해 (중간에 하나라도 조건에 맞지 않으면 돌아가는 백트래킹 덕분에) N번째 위치까지 모두 탐색한 경우에는 경우의 수++ 가능하다.

 

 

최종 코드

import java.util.Scanner;

public class Main {
    private static int count;
    private static int N;
    private static int[] positions;

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

        N = scanner.nextInt();
        count = 0;

        for (int i = 1; i <= N; i++) {
            positions = new int[16];
            positions[1] = i;
            dfs(1);
        }

        System.out.println(count);
    }

    private static void dfs(int depth) {
        if (depth == N) {
            count++;
        } else {
            for (int i = 1; i <= N; i++) {
                if (isPossible(i, depth + 1)) {
                    positions[depth + 1]  = i;
                    dfs(depth + 1);
                }
            }
        }
    }

    private static boolean isPossible(int number, int depth) {
        for (int i = 1; i < depth; i++) {
            if (positions[i] == number) {
                return false;
            }

            if (Math.abs(positions[i] - number) == Math.abs(i - depth)) {
                return false;
            }
        }

        return true;
    }
}