백준 9663번: N-Queen[JAVA]

백준 9663번: N-Queen[JAVA]

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

9663번: N-Queen

 

[정답코드]

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

public class Main {
    static int N;
    static int[] arr;
    static int count = 0;

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        arr = new int[N];

        dfs(0);
        System.out.println(count);

        br.close();
    }

    public static void dfs(int depth) {
        if (depth == N) {
            //depth가 N까지 도착하면 return
            count++;
            return;
        }
        for (int i = 0; i < N; i++) {
            arr[depth] = i;
            if (possible(depth)) {
                // 모든 조건에 통과하면 다음 depth탐색
                dfs(depth + 1);
            }
        }
    }

    public static boolean possible(int col) {
        for (int i = 0; i < col; i++) {
            // 같은 행인지
            if (arr[i] == arr[col]) {
                return false;
            }
            //대각선방향에 존재하는지
            else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
                return false;
            }
        }
        // 같은행에도 없고 대각선방향에도 없으면 true
        return true;
    }
}

 

[설명]

N-Queen 문제는 대표적인 백트래킹 알고리즘 문제이다. 체스룰을 안다면 알수있듯이 퀸은 상하좌우,대각선방향으로 움질일 수 있다. 문제에서는 서로 공격할 수 없는 경우의 수 이기 때문에 각 퀸들이 같은행, 같은열에 존재하지 않고 해당 위치에서 대각선방향에 존재해서는 안된다.

dfs, 백트래킹 알고리즘으로 풀 수 있다.

 

[그림 해석]

 

먼저 1행1열에 퀸을 놓는다. 그 다음 depth로 간다. 2번째 퀸은 2행1열에 놓지만 같은열에 존재하기 때문에 바로 탐색을 종료한다. 다시 2번째 퀸을 2행2열에 놓아본다. 이번엔 대각선에 위치하기 때문에 탐색을 종료한다. 이번엔 2행3열에 놓아보니 놓을 수 있는 위치이다. 다음 depth로 이동한다. 이를 반복하다 정답을 찾을경우 return 한다.

 

간단히 설명하자면

정답을 찾기위해 depth++ 하며 탐색을 하고, 정답이 아닐경우 다시 돌아온다.