[JAVA] 백준 9663번 : N-Queen

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

9663번: N-Queen

---

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N, answer = 0;
    static int[] col;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        col = new int[N];
        Arrays.fill(col, -1);

        for (int i = 0; i < N; i++) {
            col[i] = 0;
            putQueen(0);
            col[i] = -1;
        }
        System.out.println(answer);
    }

    private static void putQueen(int r) {
        if(r == N-1){
            answer++;
            return;
        }
        for (int i = 0; i < N; i++) {
            if(col[i] != -1) continue;
            if (isDiagonal(r + 1, i)) continue;
            col[i] = r + 1;
            putQueen(r + 1);
            col[i] = -1;
        }
    }

    private static boolean isDiagonal(int r, int c) {
        for (int i = 0; i < N; i++) {
            if(col[i] != -1){
                if(col[i]+i == r+c) return true;
                if(col[i] - i == r-c) return true;
            }
        }
        return false;
    }
}

💡 백트래킹

풀이

• 조건
  • 체스판 크기 : N * N
  • 퀸이 서로 공격할 수 없게 놓는다 == 같은 열, 같은 행에 퀸을 둬서는 안됨
  • 퀸을 둔 위치와 같은 열, 행, 대각선 상에 다른 퀸을 두면 안됨
• 처음 시도
  • 처음엔 왼쪽, 오른쪽 대각선 체크를 위해 퀸을 둔 곳 x+y, x-y 값을 각각 Set에 저장해 체크하는 방식으로 진행함
  • 시간 복잡도는 괜찮았지만 메모리 초과 발생 → Set을 별도로 생성해 관리한게 문제인 것 같았다

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static int N, answer = 0;
    static boolean[] col;
    static Set<Integer> leftD = new HashSet<>();
    static Set<Integer> rightD = new HashSet<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        col = new boolean[N];
        for (int i = 0; i < N; i++) {
            col[i] = true;
            leftD.add(i); rightD.add(-i);
            dfs(0);
            leftD.remove(i); rightD.remove(-i);
            col[i] = false;
        }
        System.out.println(answer);
    }

    private static void dfs(int r) {
        if(r == N-1){
            answer++;
            return;
        }
        for (int i = 0; i < N; i++) {
            if(col[i]) continue;
            if (isDiagonal(r + 1, i)) continue;
            col[i] = true;
            leftD.add(r + 1 + i); rightD.add(r + 1 - i);
            dfs(r + 1);
            leftD.remove(r + 1 + i); rightD.remove(r + 1 - i);
            col[i] = false;
        }
    }

    private static boolean isDiagonal(int r, int c) {
        int left = r + c;
        int right = r - c;
        return leftD.contains(left) || rightD.contains(right);
    }
}

• 다른 방식으로 시도
  
  • 각 배열에 퀸 위치 저장 한 후 직접 대각선에 있는지 계산함
  • col 배열의 인덱스는 column 위치를, col[idx] 값은 row 위치를 기록

---

💬 N-Queen 많이 풀었는데... 몇 달도 안됐다고 벌써 버벅거린다ㅠㅠ 백트래킹 다시 공부하자..