[백준 9663] Java - N-Queen

 

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

 

 

 

N-Queen

 

 

1)  문제

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

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

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

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

 

 

2)  예시

예제입력 1:

8

예제출력 1: 

92

 

 

 

 

 

3)  풀이

 

* 핵심 조건
1. 퀸은 가로, 세로, 대각선으로 이동 가능
2. 즉, 서로 같은 행, 열, 대각선에 두면 안 됨
3. 퀸 N개를 서로 공격하지 않도록 한 개씩 배치

 

 

* 아이디어
핵심 전략: 백트래킹 + 한 줄씩 퀸 배치
1. 행 단위로 한 줄씩 퀸을 배치
2. 이미 배치한 퀸들과 열, 대각선 충돌 여부를 확인
3. 조건에 맞으면 다음 줄로 진행 (재귀 호출)
4. 모든 퀸을 배치했으면 count++

 

 

 

4)  코드

//DFS + 백트래킹 방식으로 N-Queen 문제를 푼 구현

import java.util.Scanner;
// Scanner 클래스를 불러옴

public class Main {
// Main 클래스 선언
    static int N;
    // 체스판의 크기 (N × N)이며, 동시에 퀸의 개수도 의미
    static int count = 0;
    // 정답 경우의 수를 저장하는 변수
    static int[] col;
	// col[row] = x는 row행의 퀸이 x열에 배치

    public static void main(String[] args) {
    // 자바 프로그램의 시작점 main 메소드
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
		// 체스판의 크기 N을 사용자에게 입력받음
        col = new int[N];
        // 크기 N짜리 배열을 만들어 각 행의 퀸이 어디 열에 위치했는지를 저장
        solve(0); 
        // DFS 기반으로 퀸을 한 줄씩 배치하는 재귀 함수를 호출,  0번째 행부터 시작
        System.out.println(count);
    }

    public static void solve(int row) {
    // 현재 row번째 행에 퀸을 배치하기 위한 함수
        if (row == N) {
        // 기저 조건(Base case): row가 N에 도달했다는 건, 퀸을 N개 모두 배치했다는 의미
            count++;
            return;
            // 올바르게 퀸을 배치한 경우이므로 경우의 수를 증가시키고, 호출을 종료
        }

        for (int i = 0; i < N; i++) {
        // 현재 row행에 대해 가능한 열 위치(0~N-1)를 모두 시도
            col[row] = i;
            // 현재 row행에 i열에 퀸을 배치
            if (isValid(row)) {
            // 현재 배치된 위치가 기존 퀸들과 충돌하지 않는 유효한 위치인지 검사
                solve(row + 1); // 다음 행으로 진행
            }
        }
    }

    public static boolean isValid(int row) {
    // row행의 퀸이 기존 퀸들과 충돌하지 않는지 검사하는 함수
        for (int i = 0; i < row; i++) {
            // 현재 행 이전의 모든 행에 대해서 충돌 검사를 수행
            // 퀸은 한 행에 하나씩만 배치되므로 이전 행만 비교하면 충분
            // 같은 열에 있거나, 대각선에 있으면 false
            if (col[i] == col[row]) return false;
            // 같은 열에 이미 퀸이 존재한다면 충돌하므로 false 반환
            if (Math.abs(row - i) == Math.abs(col[row] - col[i])) return false;
            //두 퀸이 대각선에 위치한 경우 (행 차이 == 열 차이) → 충돌 발생 → false 반환
        }
        return true;
    }
}

 

 

 

 

 

N = 4일 때 N-Queen 문제의 DFS 탐색 트리 시각화

 

위 이미지에서 1,3은 0행 1열, 1행 3열에 퀸이 놓였다는 의미

 

만약 N = 4일 때 N-Queen 문제의 정답(해결 가능한 배치 수)는 2가지

1) 첫번째

. Q . .
. . . Q
Q . . .
. . Q .

 

배치 위치:

• (0,1)
• (1,3)
• (2,0)
• (3,2)

2) 두번째

. . Q .
Q . . .
. . . Q
. Q . .

 

배치 위치:

• (0,2)
• (1,0)
• (2,3)
• (3,1)

 

 

 

 

 

 

 

5)  리뷰

퀸이 대각선까지 공격한다는 조건 때문에 구현이 막막했는데,
행마다 퀸을 하나씩 놓고, 유효한 경우만 다음 행으로 재귀 호출하는 방식과 백트래킹을 이용하니 해결할 수 있어서 뿌듯했습니다.