[백준] N-Queen - 9663

<문제>

• 크기가 nxn인 체스판 위에 퀸 n개를 서로 공격할 수 없게 놓는 문제
• n이 주어졌을 때, 퀸을 놓는 방법의 수 구하기

<입력>

• 첫째 줄에 n 입력

<출력>

• 경우의 수 출력
• ex) n: 8 ⇒ 경우의 수: 92

<알고리즘>

• 퀸은 상하좌우, 대각선 어느 방향이든 이동 가능, 심지어 원하는 칸수만큼 맘대로 이동 가능
• 일단 서로 잡아먹히는 지 아닌지 확인해봐야 하므로 완전탐색해야함
• 이 때, 잡아먹힌다면 원래자리로 돌아가서 다른 곳으로 재탐색해야하므로 백트래킹(dfs)사용

<내 생각>

• 'ㄱ' 자로 안 겹치게 해야지 어느 곳도 공격할 수 없다.
• 각 열과 행에 1개씩만 있어야 한다.
• 근데 이걸 어떻게 코드로 한번에 해결해야하나??

<실제 알고리즘>

• 한번에 하는 게 아니라 행을 먼저 배치하고 열을 그 후에 배치한다.
  • 배치할 때, 이 위치에 놓을 수 있는 지 항상 검사한다.
• 재귀탐색을 통해 가능한 배치 횟수를 계산한다.
• 백트래킹 기법을 사용해야지 퀸이 충돌하면 바로 되돌아가서 다른 경로를 시도하므로 효율성이 증가한다.
  • 비교적 간결한 코드를 사용한다.(재귀호출을 통해 모든 가능한 배치를 탐색하므로)

<전체코드>

import java.io.*;

public class Main {
    static int n;
    static int[] board;
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n];
        nQueen(0);
        System.out.println(count);
    }
    static void nQueen(int row) {
        if(row == n) { //현재 행이 n이면 모두 배치한 것이므로 count 증가
            count++;
            return;
        }
        for(int col=0; col<n; col++) { //현재 행에 대한 모든 열 순환
            if(isSafe(row, col)) { //해당 행,열에 배치해도 되는 지 확인
                board[row] = col; //위치 저장
                nQueen(row+1); //다음행으로 이동(재귀)
            }
        }
    }
    static boolean isSafe(int row, int col) {
        for(int i=0; i<row; i++) {
            if(board[i] == col) { //같은 열에 퀸이 존재하는 지
                return false;
            }
            if(Math.abs(board[i]-col) == Math.abs(i-row)) { //대각선에 퀸이 존재하는지(행과 열의 차이가 동일)
                return false;
            }
        }
        return true;
    }
}