[JAVA] 백준 9663 N-Queen

9663번: N-Queen (acmicpc.net)

9663번: N-Queen

 

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

- N이 주어졌을 떄 , 퀸을 놓는 방법의 수를 구하는 프로그램 

 

문제 풀이 

 

- 백트래킹을 사용하는 문제 

- 백트래킹이란 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식 

 

- 현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 모든 경우의 수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가기 때문에 모든 노드를 확인하는 것이 아니라는 점이 브루트포스 알고리즘과의 차이점

 

2023.07.28 - [C언어/자료구조] - 5-4장 8퀸 문제

5-4장 8퀸 문제

 

퀸을 놓지 못하는 경우 

 

- 같은 열에 다른 퀸이 있는 경우 

- 왼쪽 대각선, 오른쪽 대각선에 다른 퀸이 있는 경우 

 

규칙 1. 각 열에 퀸을 1개만 배치한다.

규칙 2. 각 행에 퀸을 1개만 배치한다.

 

- flag_a는 각 행에 퀸을 배치했는지 체크 

- flag_b는 / 대각선 방향으로 퀸을 배치했는지 체크 

- flag_c는 \ 대각선 방향으로 퀸을 배치했는지 체크 

 

- 가로 방향(같은 행),\ 대각선 방향, / 대각선 방향 중 어느 하나라도 이미 퀸이 배치되었다면 그 칸에는 퀸을 놓을 필요가 없음 

 

- 1행에 퀸을 배치할지를 검토하고 1행에 퀸을 아직 배치하지 않았으므로 1행에 퀸을 배치 

- set 메서드를 재귀호출하여 다음 열인 두 번째 열에 퀸을 배치 

 

- 재귀 호출한 set(i+1) 메서드 실행이 끝나면 퀸을 j행에서 제거하기 위해 flag[j]에 아직 배치하지 않았음을 나타내는 false를 대입 

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static boolean[] flag_a; //각 행에 배치했는지 체크
    static boolean[] flag_b; // /대각선 방향으로 퀸을 배치했는지 체크 
    static boolean[] flag_c; // \대각선 방향으로 퀸을 배치했는지 체크 
    static int[] pos; //각 열에 있는 퀸의 위치 
    static int answer;
    static int n;
    
    //i열에 알맞은 위치에 퀸을 배치 
    static void set(int i, int n)
    {
        
       for(int j=0; j<n; j++)
       {
           if(flag_a[j] == false &&
             flag_b[i+j]==false &&
             flag_c[i-j+(n-1)]==false) {
               pos[i]=j; //퀸을 j행에 배치 
               if(i==n-1)
                   answer++;
               else
               {
                   flag_a[j] = flag_b[i+j] = flag_c[i-j+(n-1)] = true;
                   set(i+1,n);
                   flag_a[j] = flag_b[i+j] = flag_c[i-j+(n-1)] = false;
               }
           }
       }
    }
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        
        flag_a = new boolean[n];
        flag_b = new boolean[2*n-1];
        flag_c = new boolean[2*n-1];
        pos = new int[n];
        
        set(0,n);
        
        bw.write(answer+"");
        
        bw.flush();
        bw.close();
        br.close();
    }
}