Skip to main content

백준9663 N-Queen

  • N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
  • N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하기
  • 퀸은 같은 행(row), 열(column), 대각선에 있으면 공격할 수 있다
  • 그래서 퀸이 서로 겹치지 않게 배치해야 한다.

입력

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

출력

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

image.png

image.png

정답 코드

package backTracking;

import java.util.Scanner;

public class backjoonNQueen {
	// 이렇게 하는 이유는 메서드 세개 모두에서 사용가능하게 하려고
	static int n;
	static int[] arr; // arr[i] = i번째 행에서 퀸이 놓인 열 위치
	static int answer = 0; // 해답 개수

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 체스판 크기, Queen의 개수
		

		// arr[i] = j는 i번째 행(row)의 퀸이 j번째 열(column)에	있다는 의미
		// arr 배열의 인덱스는 행, 값은 열
		int[] arr = new int[n];
		
		dfs(0); // 0번째 행부터 시작
		System.out.println(answer);		
	}
	
	static void dfs(int row) {
		// n은 체스판 크기이자 퀸 개수
		// 즉, 0 ~ n-1행까지 퀸을 다 놓았을 때
		// row == n 이면 row == 4이까 0~3행에 퀸을 다 놓은 상태
		// 이 시점에서 더 이상 행을 내려가서 퀸을 놓을 필요가 없음
		// 따라서 return; 으로 현재 DFS 호출 종료 → 이전 행으로 돌아감
		if (row == n) { // row == n → 모든 행에 퀸을 놓았다 → 해답 1개 완성 ★
			answer++;
			return; // 이전 행으로 돌아감 ★
		}
		
		for (int col = 0; col < n; col++) {
			arr[row] = col; // row행 col열에 퀸 노힉
			if (isPossible(row)) { // 지금까지 놓은 퀸들이 서로 공격하지 않으면
				dfs(row + 1); // 다음 행으로 이동
			}
		}
	}

	private static boolean isPossible(int row) {
      for (int i = 0; i < row; i++) {
        // 같은 열에 이미 퀸이 있으면 실패
        // 여기서 arr[i]는 이미 놓은 퀸들의 열 위치(과거 기록)
        // arr[row]는 지금 새로 놓으려는 퀸의 열 위치(현재 진행)
        if (arr[i] == arr[row]) return false;
        // 대각선에 퀸이 있으면 실패
        if (Math.abs(row - i) == Math.abs(arr[row] - arr[i])) return false;
      }

      return true;
	}
}

1. 1차원 배열로 체스판을 어떻게 표현해?

1차원 배열로 구현하면

  1. 행 정보는 인덱스로 표현 가능함
  2. 열과 대각선만 체크하면 됨

1.1 1차원 배열 구조

arr[i] = j
  • i = 행(row)
  • j = 열(column)
  • 의미: i번째 행에 퀸이 j번째 열에 있음

예: n = 4

행

0

1

2

3

arr[i]

1

3

0

2

  • 해석:
    • 0행 → 1열
    • 1행 → 3열
    • 2행 → 0열
    • 3행 → 2열

이 배열 하나만으로 체스판 상태를 완전히 표현 가능하다고 한다.

1.2 같은 열 체크

  • 새로 퀸을 놓을 행 row에서 열 col을 선택할 때
  • 이미 놓인 퀸들과 같은 열인지 확인하기
for (int i = 0; i < row; i++) {
    if (arr[i] == col) return false; // 같은 열이면 놓을 수 없음
}

1.3 대각선 체크

  • 대각선은 행 차이 == 열 차이 인 경우 공격 가능

수식

for (int i = 0; i < row; i++) {
    if (Math.abs(i - row) == Math.abs(arr[i] - col)) return false;
}

대각선 규칙

ChatGPT Image 2025년 9월 5일 오전 01_53_40.png
  • 체스판에서 대각선 방향은 두 종류:
    1. ↘ 아래 오른쪽
    2. ↙ 아래 왼쪽
  • 체스판에서 ↘, ↙ 방향은 항상 “행과 열 차이가 같다”는 특징이 있음
  • 행과 열 차이를 같이 이동하면 대각선이라고 생각
  • 대각선에 위치한 두 칸은 다음이 항상 성립
|행 차이| = |열 차이|
Back to top