[백준 9663] N-Queen (Backtracking)

[백준 9663] N-Queen

문제 출처 : 링크

백트래킹을 활용하는 가장 유명한 백준 문제가 N-Queen이다.

체스에서 존재하는 '퀸'이 서로 공격할 수 없도록 체스판에 둘 수 있는 방법의 수를 구해야 한다.

퀸은 체스에서 가장 강력한 존재로, 자신이 위치한 곳에서 가로 줄, 세로 줄, 대각선을 모두 움직일 수 있다.

N * N 체스판에서 퀸들이 서로 공격하지 못하는 위치를 찾는 것이 문제의 핵심이다.

체스판이라 2차원 배열로 접근해야 된다고 생각할 수 있지만, 이 문제는 1차원으로 해결이 가능하다.

왜냐하면, 어차피 하나의 열에 퀸 하나를 두면, 해당 열에는 추가로 더 놓을 수 없기 때문이다.

(즉, 하나의 열마다 하나의 퀸만 놓으면 됨)

우선 Queen에 대한 Class를 만들자

class Queen {
    int n; // n*n
    int[] col; // 열
    
    Queen(int n){
        this.n = n;
        col = new int[n];
    }
}

체스판의 길이에 해당하는 n 값을 받게 되면, Queen 클래스를 생성시키고 n만큼의 col 배열을 만들어낼 것이다.

이제 백트래킹을 이용해서, 가능한 경우의 수를 모두 찾아야 한다.

public static void backtracking(Queen q, int level){
    if(level == q.n){ // 같아지면 경우의 수 증가
        count++;
        
        /*
        for (int i = 0; i < q.n; i++) {
            System.out.print(q.col[i] + " ");
        }
        System.out.println();
        */
    }
    else {
        for (int i = 0; i < q.n; i++) {
            q.col[level] = i;
            
            if(check(q, level)){
                backtracking(q, level+1);
            }
        }
    }
}

check 메소드는, boolean 형으로 만들어서 퀸이 지나갈 수 있는 곳인지 아닌지를 판별해주는 역할을 한다

public static boolean check(Queen q, int level){
    for (int i = 0; i < level; i++) {
        //같은 행과 열에 있거나 대각선에 있을 경우 false
        if(q.col[i] == q.col[level] || Math.abs(level - i) == Math.abs(q.col[level] - q.col[i])){
            return false;
        }
    }
    
    return true;
}

이렇게 해서 N * N의 체스판의 퀸을 놓을 수 있는 경우의 수를 백트레킹을 활용해 구할 수 있다

전체 소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Queen {
    int n; // n*n
    int[] col; // 열
    
    Queen(int n){
        this.n = n;
        col = new int[n];
    }
}
 
public class Problem9663 {
    
    static int count = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        Queen q = new Queen(n);
        
        backtracking(q, 0);
        
        System.out.println(count);
    }
    
    public static void backtracking(Queen q, int level){
        if(level == q.n){ // 같아지면 경우의 수 증가
            count++;
            
            for (int i = 0; i < q.n; i++) {
                System.out.print(q.col[i] + " ");
            }
            System.out.println();
            
        }
        else {
            for (int i = 0; i < q.n; i++) {
                q.col[level] = i;
                
                if(check(q, level)){
                    backtracking(q, level+1);
                }
            }
        }
    }
    
    public static boolean check(Queen q, int level){
        for (int i = 0; i < level; i++) {
            //같은 행과 열에 있거나 대각선에 있을 경우 false
            if(q.col[i] == q.col[level] || Math.abs(level - i) == Math.abs(q.col[level] - q.col[i])){
                return false;
            }
        }
        
        return true;
    }
 
}