[백준 9663] N-Queen (Java 풀이)

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

9663번: N-Queen

 

유명한 백트래킹 문제인 N-Queen입니다.

미루고 미루다 복습하는 차원에서 강의를 보고 문제를 풀었습니다.

 

만약, N이 8이라면 8x8, 즉 64칸의 체스판에서 8개를 놓는 경우의 수를 구한다면

64 C 8 (4억이 넘어감) 의 경우의 수가 나옵니다.

 

문제는 정말 퀸이 놓일 수 있는 자리만 구하라고 하였으니

백트래킹, 즉 가지치기를 해줘야 합니다.

 

문제 풀이 프로세스

퀸은 체스에서 가장 쎈 놈으로, 상하좌우 양 대각선 전부 이동이 가능합니다.

 

만약 한 개의 행에 퀸이 놓였다면 그 행에는 또 다른 퀸이 놓일 수 없습니다. 이미 놓인 퀸에게 위협받기 때문이죠.

따라서 굳이 2차원 배열을 만들지 않고 1차원 배열만 생성하면 됩니다.

 

저는 R이라는 배열을 만들었습니다.

1행부터 시작할 것이므로 N+1의 크기로 만들어줍니다.

R = new int[N + 1];

예를 들어, R[1] = 3 이라면 1행의 3열에 퀸이 놓였다는 뜻입니다.

R[2] = 2 라면 2행 2열에 퀸이 놓였다는 뜻이 되겠죠.

즉, R의 인덱스가 퀸이 놓일 행이 되고, 인덱스에 할당된 값이 열이 되는 것입니다.

R의 1~N까지 퀸을 놓아볼 겁니다.

 

아직 퀸이 놓이지 않았으므로, findQueen 메서드의 인자로 0을 넣어 호출합니다.

findQueen(0);

 

다음은 findQueen의 기본 로직입니다.

    private static void findQueen(int n) {
        if (!promising(n)) return;

        if (n == N) {
            cnt++;
            return;
        }

        for (int i = 1; i <= N; i++) {
            R[n+1] = i;
            findQueen(n + 1);
        }
    }

 

전체 코드는 다음과 같습니다.

전체 코드

package SWEA알고리즘정주행.백트래킹;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_BJ_9663_NQueen {
    static int N;
    static int[] R;
    static int cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        R = new int[N+1]; // R 배열 만들기

        findQueen(0);
        System.out.println(cnt);
    }

    private static void findQueen(int n) {
        if (!promising(n)) return;

        if (n == N) {
            cnt++;
            return;
        }

        for (int i = 1; i <= N; i++) {
            R[n+1] = i;
            findQueen(n + 1);
        }
    }

    private static boolean promising(int n) {
        for (int i = 1; i < n; i++) {
            if (R[n] == R[i] || Math.abs(n - i) == Math.abs(R[n] - R[i]))
                return false;
        }
        return true;
    }
}

 

사실 얼릉 자야 해서 쓰다 말았습니다,, 다음에 추가할게요~!ㅋㅋㅋ