[백준/자바] 9663 : N-Queen

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

9663번: N-Queen

---

N퀸 문제는 N x N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

주로 8퀸 문제로 불리는 이 문제는 재귀 알고리즘을 이해하기 위한 예제로 자주 사용된다.

N퀸 문제를 해결하기 위한 조건은 다음과 같다.

 

1. 각 열에 퀸을 1개만 배치한다.
   • 퀸 배치 함수의 인수 겹치지 않는 수(i: 열)을 넣는다.
2. 각 행에 퀸을 1개만 배치한다.
   • for문의 변수가 행 번호(j)로 flag 조건에 따라 알맞는 값을 넣는다.
3. 같은 대각선 상에 1개의 퀸만 배치한다.
   • 대각선 별로 번호를 붙이면 0 ~ N-1
   • 위 대각선: 행 + 열(i + j)값이 같으면 같은 대각선에 위치
   • 아래 대각선: 열 - 행 + N - 1값이 같으면 같은 대각선에 위치

퀸을 1개 배치하고 나서 문제를 N개의 부분문제로 나눠 퀸을 배치하는 작업을 반복한다.

 

체스판을 생각하면 보통 2차원 배열을 생각하겠지만 해당 문제에서는 하나의 열 및 행에 1개의 값만 존재하므로 2차원 배열로 구현했을 경우 대부분의 값이 0(퀸이 위치하지 않음)일 것이다.

따라서 1차원 배열의 인덱스와 값을 행, 열로 표현해 간단하게 구현할 수 있다.

 

풀이 코드는 다음과 같다.

import java.util.Scanner;

public class Main {

   static boolean[] flag_row; // 각 행에 퀸을 배치했는지 확인
   static boolean[] flag_up; // 위 대각선에 퀸을 배치했는지 확인
   static boolean[] flag_down; // 아래 대각선에 퀸을 배치했는지 확인
   static int[] pos; // 각 열에 있는 퀸의 위치 -> pos[1] = 2 : 1열 2행에 퀸 위치
   static int count = 0;
   static int N;

   public static void main(String[] args) {
       // TODO Auto-generated method stub
       Scanner sc = new Scanner(System.in);
       N = sc.nextInt();
       
       flag_row = new boolean[N];
       flag_up = new boolean[2*N-1];
       flag_down = new boolean[2*N-1];
       pos = new int[N];

       set(0);
       System.out.println(count);
       sc.close();
   }

   static void set(int i) { // i열 j행
       for(int j = 0; j<N; j++) {
           // 같은 행, 위/아래 대각선에 퀸 위치하는지 확인 -> 없으면 false
           if(flag_row[j] == false
               && flag_up[i+j] ==false
               && flag_down[i-j+N-1] == false) {
               pos[i] = j; // 퀸을 i열 j행에 배치
               if(i == N-1) // 모든 열에 배치했으면 방법의 수 + 1
                   count += 1;
               else {
                   // 퀸을 배치했으므로 true로 바꾼 후 다음 열에서 퀸 배치 작업
                   flag_row[j] = flag_up[i+j] = flag_down[i-j+(N-1)] = true;
                   set(i+1);
                   flag_row[j] = flag_up[i+j] = flag_down[i-j+(N-1)] = false; // 퀸을 j행에서 제거
               }
           }
      }
   }
}

 

* 행, 대각선 별 flag가 아닌 Possibility라는 판별함수를 따로 작성하는 방법도 있음

참고: https://velog.io/@ilil1/%EB%B0%B1%EC%A4%80-9663%EB%B2%88-java