[백준] 9663번 N-Queen- Java

[백준] 9663번 N-Queen- Java

 

문제 출처

www.acmicpc.net/problem/9663

9663번: N-Queen

---

※ 풀이

 

체스판 위에서 퀸을 놓되 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제이다.

 

필자는 재귀함수와 백트래킹을 이용하여 풀었다.

재귀함수 내 알고리즘은 다음과 같다

 

1. 놓으려는 해당 칸이 놓아도 되는 곳인가?

-> 안되면 0반환

 

2. 놓아도 되는 곳이라면 이 칸이 마지막 행인가?

-> 마지막 행이라면 1 반환(경우의 수로 카운트)

 

3. 마지막 행이 아닐 경우 다음 행의 첫 열부터 마지막 열까지 반복문을 통해 queens 함수 재귀 호출

 

 

그리고 여기서 해당 칸이 놓아도 되는 곳인지를 판별하는 isPromised 함수를 제작하였다.

isPromised 함수는 크게 두가지를 통해 놓아도 되는 곳인지를 판별한다.

 

1. 해당 칸의 같은 행에 이미 놓은 말이 있는가?

-> 이미 놓은 말의 정보를 저장하는 cols 배열을 통해 판별

 

2. 해당 칸이 이미 놓은 말의 대각선에 존재하는가?

-> 만약 이미 놓은 말(x,y 라고 하자)이 지금 놓을 말(a,b 라고 하자)과 대각선에 존재하는 경우 다음과 같은 특징을 가진다.

* (a-x)=(y-b) 가 성립한다.

해당 특성을 이용하여 대각선 여부를 판별하면 된다.

 

 

 

---

※ 소스코드

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        //input
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] cols = new int[n + 1];

        int answer = 0;
        for (int i = 1; i <= n; i++) {
            cols[1] = i;
            answer += queens(n, cols, 1);
        }

        System.out.println(answer);
    }

    public static int queens(int n, int[] cols, int level) {
        if (!isPromised(cols, level)) {
            return 0;
        } else if (level == n) {
            return 1;
        } else {
            int sum = 0;
            for (int i = 1; i <= n; i++) {
                cols[level + 1] = i;
                sum += queens(n, cols, level + 1);
            }
            return sum;
        }
    }

    public static boolean isPromised(int[] cols, int level) {
        for (int i = 1; i < level; i++) {
            if (cols[i] == cols[level]) {
                return false;
            }
            else if (level - i == Math.abs(cols[level] - cols[i])) {
                return false;
            }
        }
        return true;
    }
}