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

N-Queen

퀸은 상하좌우 대각선 다 움직일 수 있는 체스에서 만능피스이다.

따라서 체스 게임에서 가장 핵심인 피스라고 볼 수 있는데 이러한 퀸을 서로 이동 범위가 겹치지 않게 놓는 경우의 수를 구하는게 이번 문제의 목표이다.

처음에는 체스판 그대로 생각을 하여 2차원 배열의 한 열씩 퀸을 놓고 퀸의 이동 범위에는 못 놓게 값을 변경시켜가면서 백트래킹 방식으로 구현을 했다.

하지만 퀸의 이동범위중 대각선에 대해 처리하는데 어려움이 있었고, 이 부분을 해결하는데 오랜 시간 걸렸다.

결국 대각선 이동범위에 대한 처리는 실패했다.

하지만 이 문제를 체스판처럼 2차원 배열이 아니라 1차원으로 풀 수 있겠다는 생각이 들었다. 앞서 한 열씩 처리하던걸 1차원 배열로 만들고 피스가 놓이는 열을 배열의 인덱스 행을 그 인덱스의 값으로 해주면 2차원이 1차원으로 변하고 쉽게 풀이할 수 있다.

풀이는 다음과 같다.

1. 재귀호출을 통하여 cnt==n이 될 때까지 반복한다. 만약 피스를 놓치 못하는 경우가 발생하면 cnt==n이 안되니 경우의 수에서 제외할 수 있다.
2. 지금 놓을 퀸이 다른 퀸과 이동범위가 겹치지는 않는지 검사해야한다.

1은 재귀호출이기 때문에 간단하다. 문제는 2인데 앞서 2차원 배열로 풀이할 때도 이동범위가 문제였는데 1차원도 마찬가지였다.

하지만 1차원이기때문에 생각하기에는 편했고 그래서 쉽게 풀었던 것 같다.

현재 열에 퀸을 놓을때 먼저 앞서서 자신이 놓으려는 행에 퀸이 있는지 검사하고 이어 대각선 부분도 검사한다.
대각선 부분을 검사할 때 행의 차이와 열의 차이가 같으면 대각선 상에 놓였다고 생각하면 된다.

코드

import java.io.*;

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static boolean[][] visit;
    static int n, m;
    static int[][] graph;
    static int ans = 0;
    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));
        String[] nums = br.readLine().split(" ");
        n = Integer.parseInt(nums[0]);
        chess = new int[n];

        dfs(0);
        bw.write(ans + "\n");
        br.close();
        bw.close();
    }

    private static void dfs(int cnt) {
        if (cnt == n) {
            ans++;
            return;
        }
        for (int i = 0; i < n; i++) {
            chess[cnt] = i;
            if (check(cnt)) {
                dfs(cnt + 1);
            }
        }
    }

    private static boolean check(int cnt) {
        for (int i = 0; i < cnt; i++) {
            if (chess[cnt] == chess[i])
                return false;
            else if (Math.abs(cnt - i) == Math.abs(chess[cnt] - chess[i]))
                return false;
        }
        return true;
    }
}