문제

• 링크

  title: "코딩테스트 연습 - N-Queen"
  image: "https://image.freepik.com/free-vector/landing-page-template-for-a-website_23-2147782747.jpg"
  description: "가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다."
  url: "https://arc.net/l/quote/krooqkxt"
  

---

문제 풀이

문제 접근

• 백트래킹을 사용하여, 퀸을 놓을 수 있는 자리에 놓아간다.

  간단한 수도 코드 정리

  ```pseudocode 함수 solution(n): 열과 대각선을 체크할 배열 초기화 백트래킹 함수 호출 (첫 번째 행부터 시작) 가능한 배치 개수 반환

함수 backtrack(현재 행, n): 만약 모든 행에 퀸을 배치했다면: 배치 개수 증가 반환

각 열을 순회하며:
    만약 현재 열 또는 대각선이 사용 중이라면:
        건너뛰기

    퀸을 현재 위치에 배치
    다음 행으로 이동 (재귀 호출)
    퀸을 제거 (백트래킹)

---
## 풀이 코드
```java
class Solution {
    private int count = 0; // 가능한 배치 개수
    private boolean[] col;  // 열 체크
    private boolean[] diag1; // \ 방향 대각선 체크
    private boolean[] diag2; // / 방향 대각선 체크

    public int solution(int n) {
        col = new boolean[n];
        diag1 = new boolean[2 * n - 1];
        diag2 = new boolean[2 * n - 1];

        backtrack(0, n); // 첫 번째 행부터 배치 시작
        return count;
    }

    private void backtrack(int row, int n) {
        if (row == n) { // 모든 행을 채웠다면 경우의 수 증가
            count++;
            return;
        }

        for (int c = 0; c < n; c++) { // 각 열을 순회하며 퀸 배치 가능 여부 확인
            if (col[c] || diag1[row + c] || diag2[row - c + (n - 1)]) {
                continue; // 현재 열 또는 대각선이 이미 사용 중이면 건너뛰기
            }

            // 퀸 배치
            col[c] = diag1[row + c] = diag2[row - c + (n - 1)] = true;

            // 다음 행으로 이동
            backtrack(row + 1, n);

            // 퀸 제거 (백트래킹)
            col[c] = diag1[row + c] = diag2[row - c + (n - 1)] = false;
        }
    }
}

---