[백준 9663] N-Queen(Java)

문제 링크 : https://www.acmicpc.net/problem/9663

이 문제는 접근 방식을 다르게 하여 문제를 풀어야 합니다. 가장 직관적으로 문제를 풀 수 있는 방법은 2차원 배열을 만든 후 퀸을 하나하나 움직이면서 퀸이 존재하지 않는 경우 퀸을 추가하는 방식의 백트래킹으로 문제를 푸는 방법입니다. 하지만 저는 해당 방식으로 진행했을 때 결과값이 정상적으로 출력되지 않아 다른 방법을 생각해보았습니다.

우선 이 문제의 가장 키 포인트는 퀸의 위치를 체크하는 배열을 2차원 배열이 아닌 1차원 배열로 설정할 수 있다는 점입니다. 퀸의 특성 상 한 줄에 한 개만 놓을 수 있으므로 2차원 배열로 진행하더라도 결국 한 줄에 한 개의 값만 추가됩니다. 따라서 퀸의 가로 위치값 배열[퀸의 세로 위치값] = 퀸의 가로 위치값 과 같은 식으로 1차원 배열로 퀸의 위치를 표현할 수 있습니다.

퀸을 놓는 방법의 수를 구하는 로직은 다음과 같습니다.

1. 첫 번째 줄부터 차례대로 탐색
2. 현재 줄에서 퀸을 놓을 수 있는지 가로 방향으로 확인하기 위해 현재 줄의 가로값을 1씩 차례대로 증가
3. 만약 현재 가로값이 퀸을 둘 수 있는 위치라면 다음 줄로 이동

이 때 퀸을 둘 수 있는 위치인지 판별할 수 있는 로직은 다음과 같습니다.

1. 현재 줄 이전의 줄의 가로값과 세로값을 차례대로 탐색
2. 만약 이전 줄과 가로값이 같다면 같은 세로선 상에 놓이게 되므로 퀸을 놓을 수 없음
3. 만약 현재 줄의 세로값과 이전 줄의 세로값의 차와 현재 줄의 가로값과 이전 줄의 가로값의 차가 같다면 N X N 의 정사각형 체스판이기 때문에 같은 대각선상에 놓기게 되어 퀸을 놓을 수 없음
4. 모든 케이스를 전부 확인했는데도 걸리는 부분이 없다면 퀸을 놓을 수 있음

따라서 위의 로직을 코드로 구현하면 아래와 같습니다.

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

public class Main {
    static int N;
    static int res = 0;
    static int[] column_num = new int[15];
    // 퀸의 특성 상 한 줄에 한 개만 놓을 수 있다.
    // 따라서 1차원 배열의 값으로 해당 row에 존재하는 퀸의 column 번호를 알 수 있다면
    // 굳이 2차원 배열을 만들어서 체크할 필요 없이 체크가 가능하다.

    static boolean canPutQueen(int curr_row_num){
        // 현재 줄 위의 있는 줄의 인덱스를 전부 비교
        for(int prev_row_num=0; prev_row_num<curr_row_num; prev_row_num++){
            // 이전 줄과 가로값이 같다면
            // 같은 세로선 상에 놓이게 되므로
            // 퀸을 놓을 수 없음
            if(column_num[prev_row_num] == column_num[curr_row_num]) return false;

            // 현재 줄과 이전 줄의 차와 가로값의 차가 같다면
            // N X N 의 정사각형 체스판이기 때문에
            // 같은 대각선상에 놓이게 되므로
            // 퀸을 놓을 수 없음
            if(Math.abs(prev_row_num - curr_row_num) == Math.abs(column_num[prev_row_num] - column_num[curr_row_num])) return false;
        }
        // 모든 케이스를 다 돌았는데도 걸리는 부분이 없다면
        // 퀸을 놓을 수 있음
        return true;
    }

    static void backtracking(int curr_row){
        // 현재 row가 끝까지 갔을 경우
        // 즉 퀸을 N개 만큼 놓았다면 리턴
        if(curr_row==N){
            res++;
            return;
        }

        for(int i=0;i<N;i++){
            // 퀸을 놓을 수 있는지 가로 방향으로 확인하기 위해
            // 현재 줄의 가로값을 1씩 증가시켜보기
            column_num[curr_row] = i;

            // 만약 현재 가로값이 퀸을 둘 수 있는 위치라면 다음 줄로 이동
            // 원래 백트래킹이라면 체크값을 재조정해야하지만
            // 현재 체크값이 반복문 안에서 매번 변경되기 때문에 재조정할 필요 없이 dfs 처럼 동작
            // 그렇지 않다면 백트래킹 실행하지 않기
            if(canPutQueen(curr_row)){
                backtracking(curr_row+1);
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        backtracking(0);
        System.out.println(res);
    }
}