[JAVA]백준 9663번: N-Queen

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

9663번: N-Queen

1. 문제 설명

 

크기가 N*N인 체스판 위에 퀸 N개가 서로 공격할 수 없게 놓는 방법의 수를 구하는 문제.

 

1<=N<15

 

2. 풀이

 

퀸은 대각선, 직선에 있는 다른 퀸을 공격할 수 있다.

 

따라서 한 라인에 한 퀸만 존재해야되며 대각선에 다른 퀸이 존재해서는 안된다.

 

맨 윗 라인부터 끝까지 퀸을 하나씩 놓아가면서 대각선이나 직선 상으로 다른 퀸이 있는지 확인해가면서 퀸을 놓는 방법의 수를 세면 된다.

 

대각선, 직선 상에 퀸이 존재하는지 알기 위해서 특정 위치의 퀸을 놓았을 때 int[][]배열을 사용하여 특정 위치의 놓은 퀸이 공격할 수 있는 위치들에 퀸의 x+1값을 저장했다.

 

다음 라인에 퀸을 놓을 때 만약 int[][]배열의 값이 0이 아니라면, 다른 퀸의 공격 범위에 있는 것이므로 피해서 다른 자리에 놓으면 된다.

 

그 다음 퀸의 위치를 옮기면, 방금 int[][]배열에 저장한 특정 위치 x,y에 놓은 퀸의 공격 범위를 0으로 초기화 하면 된다.

 

저장하고 초기화할 때 주의할 점은 기존의 퀸 공격 범위를 덮어쓰면 안된다는 것이다.

 

예를 들어, 첫번째 라인에 놓은 퀸과 세번째 라인에 놓은 퀸 두개에게 모두 공격될 수 있는 위치가 있다고 해보자.

 

이것을 세번째 라인의 퀸을 놓을 때 int[][]배열의 값을 3으로 변경해버리고, 초기화할때 이 위치의 int[][]배열의 값을 0으로 바꿔버리면 첫번쨰 라인에 놓은 퀸의 공격범위도 아닌 것으로 인식되어버리기에 다음 라인에서 이 위치에 퀸을 놓게 될 수도 있다.

 

따라서 퀸을 놓을 때 int[][]배열의 값이 0이 아니라면 값을 저장하지 않고, 0일 때만 x+1 값을 저장했다.

 

초기화할때도, int[][]배열의 값이 x+1일때만 0으로 초기화했다.

 

이런식으로 N 라인까지 연산을 수행하고 방법의 수를 구하면 된다.

 

3. 코드

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

public class Main {

    public static int N;
    public static int[][] chess;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        chess = new int[N][N];

        int ans = makeChess(-1);

        System.out.println(ans);


    }

    public static int makeChess(int x) {

        if (x == N - 1) {
            return 1;
        }

        int ans = 0;

        for (int idx = 0; idx < N; idx++) {

            if (chess[x + 1][idx] == 0) {
                fill(x + 1, idx);
                ans += makeChess(x + 1);
                cancle(x + 1, idx);
            }
        }

        return ans;

    }

    public static void fill(int x, int y) {
        // 이미 위의 인덱스에서 확인한 경우, 덮어 쓰면 안된다.

        // 대각선 왼쪽

        int idx_x = x + 1;
        int idx_y = y - 1;

        while (idx_x < N && idx_y >= 0) {
            if (chess[idx_x][idx_y] == 0) {
                chess[idx_x][idx_y] = x + 1;
            }
            idx_x++;
            idx_y--;
        }

        // 대각선 오른쪽

        idx_x = x + 1;
        idx_y = y + 1;

        while (idx_x < N && idx_y <N) {
            if (chess[idx_x][idx_y] == 0) {
                chess[idx_x][idx_y] = x + 1;
            }
            idx_x++;
            idx_y++;
        }

        // 아래
        for (int idx = x; idx < N; idx++) {
            if (chess[idx][y] == 0) {
                chess[idx][y] = x + 1;
            }
        }
    }

    public static void cancle(int x, int y) {
        // 현재 line에서 채운 것들만 다시 비운다.

        // 대각선 왼쪽

        int idx_x = x + 1;
        int idx_y = y - 1;

        while (idx_x < N && idx_y >= 0) {
            if (chess[idx_x][idx_y] == x+1) {
                chess[idx_x][idx_y] = 0;
            }
            idx_x++;
            idx_y--;
        }

        // 대각선 오른쪽

        idx_x = x + 1;
        idx_y = y + 1;

        while (idx_x < N && idx_y <N) {
            if (chess[idx_x][idx_y] == x+1) {
                chess[idx_x][idx_y] = 0;
            }
            idx_x++;
            idx_y++;
        }

        // 아래
        for (int idx = x; idx < N; idx++) {
            if (chess[idx][y] == x+1) {
                chess[idx][y] = 0;
            }
        }
    }



}