[백준] 9663: N-Queen (백트래킹) - JAVA

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

 

 

# 문제

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

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

 

# 예제

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

8

 

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

92

 

# 필요개념

우선 어떤 경우에 퀸이 공격을 할 수 있게 되는지 알고있어야 한다. 퀸은 다음과 같은 조건에서 공격할 수 있다.

• 같은 열에 있는 경우
• 같은 대각선상에 있는 경우

즉, 문제가 원하는 것은 같은 열에 있지 않고, 동시에 같은 대각선상에 있지 않는 경우의 수를 출력하라는 뜻이다. 

 

이를 파악하기 위해서는 퀸이 놓인 위치의 열과 행을 알아야 하고, 나는 이를 일차원 배열에 담았다. 배열의 인덱스는 열을 의미하고, 배열 안에 놓인 값이 행을 의미하게 하도록 했다. 이 배열의 크기는 N + 1로 해서 인덱스 1부터 값을 담았다.

 

예를 들어, {0, 2, 3, 1} 이라면 (1,3), (2,1), (3,2) 에 퀸이 자리잡고 있다는 의미이다.

 

이 배열을 이용해 대각선과 같은 열에 퀸이 있는지 확인 후, 없다면 재귀함수를 호출해 같은 작업을 반복한다. 

가독성을 위해 같은 열에 있는지 확인하는 로직과 같은 대각선에 있는지 확인하는 로직은 별도의 함수로 만들었다.

 

# Code

import java.util.*;
import java.io.*;

import static java.lang.Math.*;

public class Main {
    static int N;
    static int[] isVisit;
    static BufferedWriter bw;
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        isVisit = new int[N + 1];

        for (int i = 1 ; i <= N ; i++) {
            isVisit[i] = 1;
            backtracking(1);
            isVisit[i] = 0; 
        }
        System.out.println(answer);
    }

    private static void backtracking(int row) throws IOException {
        if (row == N) answer++;
        if (row < N) {
            for (int i = 1 ; i <= N ; i++) {
                if (!isCross(i, row) && !isSameLine(i)) {
                    isVisit[i] = row + 1;
                    backtracking(row + 1);
                    isVisit[i] = 0;
                }
            }
        }
    }

    private static boolean isSameLine(int idx) {
        for (int i = 1 ; i <= N ; i++) {
            if (isVisit[i] != 0 && idx == i) return true;
        }
        return false;
    }

    private static boolean isCross(int idx, int row) {
        for (int i = 1 ; i <= N ; i++) {
            if (isVisit[i] != 0 && (abs(idx - i) == abs((row + 1) - isVisit[i]))) {
                return true;
            }
        }
        return false;
    }

}

 

# 결과