[백준] N-Queen (Easy) - Java 30242

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

 

N-Queen 문제로 대각선을 일차원 배열 형태로 저장하여 최적화를 해줘야 한다.

 

나머지는 똑같이 백트래킹을 하면 된다.

import java.io.*;
import java.util.*;

public class BOJ30242 {

    static int n;
    static int[] lst;
    static boolean[] col;
    static boolean[] up;
    static boolean[] down;
    static List<Integer> nums;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        lst = new int[n];
        col = new boolean[n + 1];
        up = new boolean[2 * n];
        down = new boolean[2 * n];

        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            lst[i] = Integer.parseInt(input[i]);
        }

        Set<Integer> allNumbers = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            allNumbers.add(i);
        }
        for (int num : lst) {
            if (num != 0) allNumbers.remove(num);
        }
        nums = new ArrayList<>(allNumbers);
        Collections.sort(nums);

        if (!backtrack(0)) {
            System.out.println(-1);
        }
    }

    static boolean backtrack(int i) {
        if (i == n) {
            for (int num : lst) {
                System.out.print(num + " ");
            }
            System.out.println();
            return true;
        }

        if (lst[i] != 0) { // Queen already placed
            int num = lst[i];
            if (!col[num] && !up[i - num + n] && !down[i + num]) {
                col[num] = up[i - num + n] = down[i + num] = true;
                if (backtrack(i + 1)) return true;
                col[num] = up[i - num + n] = down[i + num] = false;
            }
            return false;
        }

        for (int num : nums) { // Place a Queen
            if (!col[num] && !up[i - num + n] && !down[i + num]) {
                lst[i] = num;
                col[num] = up[i - num + n] = down[i + num] = true;
                if (backtrack(i + 1)) return true;
                col[num] = up[i - num + n] = down[i + num] = false;
                lst[i] = 0;
            }
        }

        return false;
    }
}