[백준] 9663번: N-Queen

📖 문제 설명

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

💦 입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

🍩 출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

🤯 풀이 로직

1. 1번~n행까지 순열로 퀸을 놓는다.

필요한 자료형

• 퀸의 개수를 담을 변수 : int n
• 정답을 담을 변수 : int ans
• 퀸이 놓인 열을 담을 배열 : int[] col = new int[n+1]

필요한 함수

1. 순열 구하는 함수 (현재 행)

• n개를 뽑았으면
  • 정답 하나 추가한다.
  • 리턴
• n개를 뽑지 않았으면
  • 1행부터 n행까지 확인한다.
    • 현재 위치에 퀸을 놓을 수 있다고 가정한다.
    • 1행부터 현재 행의 앞까지 확인한다.
      • 놓을 수 있는지 확인하는 함수 (현재 행, 현재 열, 확인할 행, 확인할 열)
        • 놓을 수 없으면 현재 위치에 퀸을 놓을 수 없다고 체크한다.
        • 반복문을 빠져나간다.
    • 현재 위치에 퀸을 놓을 수 있으면
      • 현재 열에 퀸을 놓는다.
      • 순열 구하는 함수 (현재 행 + 1)
      • 현재 열에 퀸을 제거한다.

2. 놓을 수 있는지 확인하는 함수 (현재 행, 현재 열, 확인할 행, 확인할 열)

• 같은 열에 있으면 놓지 못한다.
• 대각선에 있으면 놓지 못한다.
• 위의 경우가 아니라면 놓을 수 있다.

대각선에 놓지 못하는 경우는 다음과 같다.
만약 (3,3)위치에 퀸이 있을 때, 대각선은 2개가 나오게 된다.

즉, 오른쪽 아래로 향하는 연두색 대각선과 왼쪽 아래로 향하는 핑크색 대각선이 생기게된다.
이때 각 좌표들을 살펴보자!
연두색 대각선 - 행과 열의 차가 똑같다.
핑크색 대각선 - 행과 열의 합이 같다.
이 규칙을 추상화하여 적용하면 됩다!

💭 회고

이전에 백트래킹 관련해서 문제 풀때 이 문제는 도저히 이해를 할 수 없었다. 문제를 보고 이게 왜 백트래킹 문제인지도 이해할 수 없었다.
드디어 1년 만(?)에 이해가돼서 진짜 너무 행복하다!!

🌠 배운것

• 좌표에서 대각선을 반복문을 통해 돌리지 않아도 오른쪽 아래로 향하는 대각선은 차가 같다는 점, 왼쪽 아래로 향하는 대각선은 합이 같다는 점을 배웠다.

🔑 코드

import java.io.*;

public class Main {
    static int n, ans;
    static int[] col;

    static boolean check(int row, int col, int checkRow, int checkCol) {
        if (col == checkCol) return true; // 같은 열에 있으면 안됨
        if (row-col == checkRow-checkCol) return true; // 오른쪽 대각선 체크
        if (row+col == checkRow+checkCol) return true; // 왼쪽 대각선 체크
        return false;
    }

    static void permutation(int row) {
        if (row == n+1) { // 각 행마다 놓았으면
            ans++; // 정답 추가
            return;
        }

        for (int i=1; i<=n; i++) {
            boolean flag = true; // 놓을 수 있다고 가정.
            for (int j=1; j<=row-1; j++) {
                if (check(row, i, j, col[j])) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                col[row] = i; // row행 col열에 i번 퀸을 놓는다.
                permutation(row + 1); // 다음 행으로
                col[row] = 0;
            }
        }
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        col = new int[n+1];
    }

    public static void main(String[] args) throws IOException {
        input();
        permutation(1); // 1번행에 놓으러 출발
        System.out.println(ans);
    }

}