백준 9663 N-Queen

🔗 백준 9663 N-Queen 

 

여덟 퀸 문제 - 위키백과, 우리 모두의 백과사전

 

📌오늘의 학습 키워드

• 백트래킹

✨공부한 내용 본인의 언어로 정리하기

• N x N에 N개의 퀸을 놓으려면 각 열에 적어도 한개의 퀸이 놓여야 한다. 

📚오늘의 회고

• • 제대로된 종료조건을 찾지 못해서 헤맸다.
  • 한개씩 퀸을 배치하고, 해당 퀸의 영향력을 MAP에 표시하고
  • 다시 그 영향력이 미치지 않는 곳을 찾아서 퀸을 놓은 후에
  • 마지막에는 나머지 빈 공간을 모두 세는 것으로 알고리즘을 만들어봤는데 
    • 😅 여기에는 퀸을 각각 다르게 본다는 치명적인 오류가 있었다.
  • 너무 시간을 오래 써서 지피티에게 도움 요청
    • N x N에 N개의 퀸을 놓으려면 각 열에 적어도 한개의 퀸이 놓여야 한다. 
    • col = 열 (같은 열 배치 방지)
    • diag1 ↘ = queen_row + c
    • diag2 ↙ = queen_row - c + N (음수 방지를 위해 N 더하기)

[🤓문제 해결 코드]

import java.io.*;

public class Main {
    static int N;
    static int total;
    static boolean[] col, diag1, diag2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        col = new boolean[N];
        diag1 = new boolean[2 * N];  // ↘ 대각선
        diag2 = new boolean[2 * N];  // ↙ 대각선

        DFS(0);
        System.out.println(total);
    }

    private static void DFS(int queen_row) {
        if (queen_row == N) {
            total++;
            return;
        }

        for (int c = 0; c < N; c++) {
            if (col[c] || diag1[queen_row + c] || diag2[queen_row - c + N]) continue;

            // 퀸을 배치
            col[c] = diag1[queen_row + c] = diag2[queen_row - c + N] = true;
            DFS(queen_row + 1);
            col[c] = diag1[queen_row + c] = diag2[queen_row - c + N] = false; // 백트래킹
        }
    }
}