99클럽 코테 스터디 11일차 TIL 백트래킹(N-Queen)

 

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

 

사용 알고리즘

DFS, 백트래킹

 

아이디어

1. 행을 DFS로 하나씩 올려가면서

2. 열과 대각선 확인

3. 마지막 행까지 왔을 때 + 1한 개수를 최종 출력

 

유의점

1. 서로 공격할 수 있는 경우는 같은 행 / 같은 열 / 같은 대각선에 위치할 때이다.

 

제출코드

package BOJ.Graph.DFS;

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

public class BOJ_9663_NQueen {

    static int n;
    static int ans;
    static int[] visited;

    public static boolean check(int x, int y){
        for(int i=1; i<n+1; i++){
            // 열 확인
            if(visited[i] == y) return false;
            // 대각선 확인
            if((x - i) == Math.abs(y - visited[i])) return false;
        }
        return true;
    }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        visited = new int[n+1];
        dfs(1);

        System.out.println(ans);
    }
}