[백준/JAVA] 9663번 : N-Queen(BackTracking, 백트래킹)

 

 

 

문제

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

9663번: N-Queen

 

 

 

 

풀이

 

백트래킹 문제이다.

체스판에서 퀸이 공격할 수 있는 위치는 상하좌우와 대각선상의 모든 위치이다.

4x4 체스판의 (0,0) 위치에 퀸 하나를 두었을 때, 퀸이 공격 가능한 위치를 그림으로 나타내면 다음과 같다.

 

즉, nxn의 판에서 퀸 n개를 모두 서로 공격할 수 없는 위치에 놓으려면 각 퀸들이 상하좌우 대각선 중 어느 곳에도 위치해서는 안된다.

이 조건을 분해해보면,

1. 각 행에는 무조건 퀸이 존재해야 하며, 반드시 1개여야 한다.
2. 각 열에는 무조건 퀸이 존재해야 하며, 반드시 1개여야 한다.
3. 각 퀸의 대각선 상에는 또 다른 퀸이 존재해서는 안 된다.

 

 

우리는 위의 세 가지 조건을 확인하면서, 퀸을 배치할 것이다.

 

 

만약, 4x4체스판에서 0번째 열의 0번째 행 위치에 퀸을 두었다면, 1번째 열에서 가능한 퀸의 위치는 2번째 행의 위치 또는 3번째 행의 위치일 것이다. 하지만 1번째 열에서 2번째 행의 위치에 퀸을 두게 된다면, 다음과 같이 3개의 퀸만을 둘 수 있다.

 

2번째 열의 퀸을 다른 곳에 둘 수는 없으므로, 1번째 열의 퀸을 두는 경우로 돌아오게 된다.

하지만 1번째 열의 퀸을 이번에는 3번째 행의 위치에 둔다 해도, 4개의 퀸을 모두 둘 수 없다는 것을 알게 될 것이다.

 

이렇듯, 다음 열에서 퀸을 둘 수 없다는 것을 알게 되면, 이전 열에서 퀸을 두는 경우를 바꾸게 된다.

 

 

 

이 과정을 코드로 구현하면, 다음 열에 공격할 수 없는 위치가 존재하고 그 위치에 퀸을 놓을 수 있으면 재귀호출을 계속하는 방식으로 구현할 수 있다. board는 리스트로 0번째 index의 값은 0번째 열의 퀸의 위치를, 1번째 index의 값은 1번째 열의 퀸의 위치를, n번째 index의 값은 n번째 열에서의 퀸의 위치를 저장하는 리스트이다. 만약, n개의 퀸이 모두 배치되었다면 count는 +1 증가한다.

public static void backTracking(int idx){
    if(idx==n){
        count++;
        return;
    }

    //현재 열의 모든 행 확인
    for(int i = 0; i<n; i++){
        if(!checkAttackable(i, idx)){
            board.add(i);
            backTracking(idx+1);
            board.remove(board.size()-1);
        }
    } 
}

 

 

공격 가능한 위치인지 확인하는 checkAttackable 메소드는 다음과 같이 구현한다.

board가 index값의 열에서 행의 위치를 저장하는 리스트이므로, board의 모든 값들은 서로 겹쳐서는 안 된다.

만약 겹치는 값이 있다면 같은 행에 다른 퀸이 존재한다는 것이므로 공격할 수 있다고 판단한다.

대각선 상에 다른 퀸이 존재한다면 두 퀸의 위치상 x좌표의 차이와 y좌표의 차이가 같다. 따라서 두 좌표의 차이가 같을 때에도 공격할 수 있다고 판단한다.

public static boolean checkAttackable(int k, int idx){
    //0번째 col이면 이전에 퀸이 없으므로 항상 공격 받지 않음
    if(idx==0) return false;

    //만약 이전에 퀸이 존재하고, 같은 행이면 공격받음
    if(board.contains(k)) return true;

    //대각선 상에 퀸이 있는지를 확인함
    for(int i = 0; i<board.size(); i++){
        int rowGap = Math.abs(k-board.get(i));
        int colGap = Math.abs(idx-i);
        if(rowGap==colGap) return true;
    }
    return false;
}

 

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int n;
    static int count = 0;
    static List<Integer> board = new ArrayList<>();

    public static void backTracking(int idx){
        if(idx==n){
            count++;
            return;
        }

        //현재 열의 모든 행 확인
        for(int i = 0; i<n; i++){
            if(!checkAttackable(i, idx)){
                board.add(i);
                backTracking(idx+1);
                board.remove(board.size()-1);
            }
        }
    }

    public static boolean checkAttackable(int k, int idx){
        //0번째 col이면 이전에 퀸이 없으므로 항상 공격 받지 않음
        if(idx==0) return false;

        //만약 이전에 퀸이 존재하고, 같은 행이면 공격받음
        if(board.contains(k)) return true;

        //대각선 상에 퀸이 있는지를 확인함
        for(int i = 0; i<board.size(); i++){
            int rowGap = Math.abs(k-board.get(i));
            int colGap = Math.abs(idx-i);
            if(rowGap==colGap) return true;
        }
        return false;
    }

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

        backTracking(0);
        System.out.println(count);
    }
}