[백준9663번] N-Queen

문제

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

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

입력

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

출력

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

예제 입력 1 복사

8

예제 출력 1 복사

92

나의 풀이

처음에는 N*N의 이차원 배열을 만들어 체스판형태에서 퀸의 위치를 표시했었다. 그러나 이렇게하게 되면 앞으로 유망한지의 여부를 확인하는 함수에서 for문이 많이 중첩이 되어서 시간초과로 문제를 풀 수 없었다. 그래서 검색을 통해서 생각을 해보니 visit함수를 1차원배열로 만들고 각각의 index는 각 행의 번호로 보고 각각의 index값에 저장되어 있는 수를 열의 번호로 생각하고 풀어보니 유망여부를 확인하는게 아주 간단해질 수 있었다. 예를들어 visit[2] = 3 이라면 2번째 행에서 퀸의 위치는 3이라는 것이다.

이제 앞에서 말하던 유망여부에 대해 말해보자면 유망하다는 것은 백트래킹의 여부를 결정지으며 현재 이 상태에서 다음으로 진행이 가능한지를 확인하는 것이다. N-Queen의 문제에서는 퀸이 공격을 할 수 있는 방법은 행, 열, 대각선으로 공격을 할 수 있으므로 앞선 열에서 같은 열, 대각선에 이미 퀸이 있는지의 여부를 확인하면 된다. 1차원 배열로 생각한다면 현재 행보다 앞선 행들에서 현재의 열값이 존재하는지를 체크하면 같은 행에 있는지 확인할 수 있고, 현재 행과 앞선 행의 차이가 현재 열의 값과 앞선 열의 차이와 같다면 대각선에 존재하는 지를 확인할 수 있다. 밑에 코드에 주석을 보면 쉽게 이해가 갈 것이다.

코드

import java.util.Scanner;

/**
 * 9663번 N-Queen
 */
public class Baeckjun9663 {
    static int[] visit;
    static int n;
    static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        visit = new int[n+1];

        nQueen(1);

        System.out.println(count);
    }

    static void nQueen(int r) {
        for (int c=1; c<=n; c++) {
            if (check(r,c)) {
                visit[r] = c;
                if (r == n) {
                    count++;
                } else nQueen(r + 1);
            }
        }
    }

    static boolean check(int r, int c) {
        for (int i=1; i<r; i++) {
              // 같은 열에 있는지 || 대각선에 퀸이 위치하고 있는지
            if (visit[i] == c || r-i == Math.abs(visit[i]-c)) {
                return false;
            }
        }
        return true;
    }