📘[백준-9663] N-Queen 백트래킹(Java)

N-Queen 문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

백트래킹

이 문제는 백트래킹을 이용해서 풀 수 있다.
백트리킹이란 “가능한 모든 방법을 탐색한다”의 아이디어를 가진다.
즉, 백트래킹은 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다가 판단되면 즉시 후보를 포기하면서 정답을 찾아가는 범용적인 알고리즘이다.
**“특정조건”을 만족하는 “모든 경우의 수”를 찾을 때 용이함!**

백트래킹의 가지치기로 문제를 풀면, 불필요한 재귀호출을 수행하지 않아 훨씬 효율적으로 답을 구할 수 있다.

입력을 받을 때에도 2차원 배열을 생각하기 쉽지만, 1차원 배열로 해결한다면 시간이 더 절약된다.

(0,2), (1,0), (2,3), (3,1) 처럼 저장하지 않고, 위 사진처럼 (2,0,3,1)처럼 퀸이 놓인 열(row)의 위치만 저장해도 충분하다.
이유는 퀸의 열이 같다면 다른 퀸이 공격할 수 있으니까!

백트래킹 절차

DFS 수행 - 유망한 노드 검토 - 서브 트리 이동 - 백트래킹 수행

1. DFS 수행
   원래대로 재귀 호출을 이용해서 계속 이동하는 DFS를 수행하여 노드를 찾는다.
2. 유망한 노드 검토
   방문한 노드를 포함해서 유망한 노드이면 서브트리로 이동하고 그렇지 않으면 백트래킹을 수행한다.
3. 서브 트리 이동
   방문한 노드의 하위 노드로 이동하여 다시 재귀를 통해 DFS를 수행한다.
4. 백트래킹 수행
   방문한 노드를 가지치기하고 상위 노드로 백트래킹 한 후 DFS를 다시 수행한다.

N-Queen 백트래킹 이용해서 풀기

체스에서 퀸은 직선과 대각선 모든 방향으로 모든 칸을 자유자제로 이동할 수 있다.
그런데 퀸끼리 놓는데, 서로 공격할 수 없게 하려면 체스판의 한 줄에는 하나의 퀸만 존재하게 된다!

그러면, 1번째 줄에 퀸 하나를 놓고 다음 줄로 넘어가 “조건에 맞게” 퀸을 다시 놓고, 다시 다음 줄로 넘어가 “조건에 맞게” 퀸을 또 놓는 방식으로 진행하면 되겠다.

[Java]코드

package Baekjoon_sds.알고리즘_기초;
import java.util.Scanner;

// N-Queen
// 1. 퀸과 인접한 칸에는 다른 퀸이 있으면 안됨 -> 검사 필요
// 2. 안전한 곳에 퀸 배치

public class N_Queen {
    public static void main(String[] args) {
        int N;
        int[] cols;
        Scanner scanner = new Scanner(System.in);
        System.out.print("");
        N = scanner.nextInt();
        cols = new int[N];

        Queen queen = new Queen(N, cols);
        for (int i = 0; i < N; i++) {
            queen.back_tracking(i);
        }
    }
}

class Queen {
    int N;
    int cols[];

    public Queen(int n, int[] cols) {
        N = n;
        this.cols = cols;
    }

    public void back_tracking(int level) {

        if (level == N) {
            for (int i = 0; i < N; i++) {
                System.out.print(cols[i]);
            }
            System.out.println();
        } else {
            for (int i = 0; i < N; i++) {
                cols[level]=i;
                if (isPossible(level)) {
                    back_tracking(level+1);
                }
            }
        }
    }

    public boolean isPossible(int level) {
        for (int i = 0; i < level; i++) {
            if (cols[i] == cols[level] || Math.abs(level - i) == Math.abs(cols[level] - cols[i])) {
                return false;
            }
        }
        return true;
    }
}

[Python]코드

def adjacent(x): # x와 i 가 같으면 행이 같은거 근데 for문을 보면 x와 i가 같을 수가 없다.
    for i in range(x): #인덱스가 행  row[n]값이 열
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i: # 열이 같거나 대각선이 같으면 false
            return False # 대각선이 같은경우는 두 좌표에서 행 - 행 = 열 - 열 이 같으면 두개는 같은 대각선상에 있다.
    return True
 
#한줄씩 재귀하며 dfs 실행
 
def dfs(x):
    global result
 
    if x == N:
        result += 1
    else:
        # 각 행에 퀸 놓기
        for i in range(N): # i 는 열번호 0부터 N 전까지 옮겨가면서 유망한곳 찾기
            row[x] = i
            if adjacent(x): # 행,열,대각선 체크함수 true이면 백트래킹 안하고 계속 진행
                dfs(x + 1)
 
# N = int(input())/
N = int(input())
row = [0] * N
result = 0
print(row)
dfs(0)
# print(row)
print(result)