[백준 BOJ 9663번] N - Queen

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

9663번: N-Queen

 

1. 문제

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

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

---

2. 입력

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

8

---

3. 출력

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

92

---

4. 풀이

 

이 문제를 풀고자 백트래킹 알고리즘을 공부를 했다. 우선 브루트포스 알고리즘처럼 모든 케이스를 확인하려면 n차 for문이 필요할 것이고 배열에 할당할 데이터 크기 또한 클 것이라 생각이 들었다. 이를 재귀를 통해 확인을 하되 안되는 중간에서부터 이미 틀려먹은 것들은 아예 잘라내고 다시 돌아가서 경우의 수를 찾고자 했다. 먼저 체스판의 크기를 입력받아 판부터 생성을 하고 nqueens라는 함수를 실행하였다.

nqueens -> 만약 매개변수가 체스판의 크기와 같다면 다 채워졌다는 뜻이니 count를 늘리고, 그렇지 않다면 그 행에 for문으로 열번호를 입력해가면서 그 열에 퀸을 두는 것이 합당한지 확인 후 합당하면 다음 행에 대한 nqueens 함수를 실행하였다.

 

promising -> 해당 함수에는 행번호가 매개변수로 입력되어 들어오고 for문을 이용해서 이 행번호 이전의 행들의 말들과 서로 공격관계가 되는지 확인 후 그렇다면 false를 return하고, for문을 다 돌았는데도 문제가 없다면 true를 return하였다.

---

5. 소스코드

import java.io.*;

class Main{

    public static int num;
    public static int [] n_board;
    public static int count = 0;

    public static void main(String []args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        num = Integer.parseInt(br.readLine());
        n_board = new int [num];
        
        nqueens(0);
        System.out.println(count);

    }

    public static boolean promising(int x){
        for(int i=0; i<x; i++){
            if(n_board[x] == n_board[i] || Math.abs(n_board[x] - n_board[i]) == Math.abs(x - i)) return false;
        }
        return true;
    }

    public static void nqueens(int x){
        if(x == num){
            count++;
            return;
        }
        for(int i=0; i<num; i++){
            n_board[x] = i;
            if(promising(x)) nqueens(x+1);
        }
    }
}

---

6. 배운 것

백트래킹 알고리즘을 내 것으로 만드는데에 굉장히 시간이 오래 걸렸다. 모두 이해한 이후엔 내 마음대로 적용할 수 있게 되었지만 머릿속으로 생각하는 가지치기법을 코드로 적용하는데에는 꽤 어려웠다. N-Queens라는 문제 자체가 백트래킹 알고리즘을 대표하는 문제이기에 정복하는 것이 필요하다고 느꼈다. 재귀 알고리즘을 if문으로 promising한지 따지고서 이용하는 방식, promising에서는 단순히 검사만 하고 안되는지 되는지를 boolean형으로 알려주는 방식... 이 2가지를 큰 가지로 생각하고서 백트래킹 문제들을 접해야겠다는 생각이 들었다.