[백준] 9663번(Java)

📖 N-Queen

[ 문제 ]

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

💡풀이

• 체스에서 Queen은 상하좌우 및 각 대각선 위치로 이동이 가능한 막강한 말이다.(필자는 체스를 몰라 이렇게 강력한 이인지 몰랐다.)
• 백트래킹 문제이기 때문에 체스판 위의 한 지점을 방문한 뒤, 그 뒤의 다른 체스판 지점들을 돌면서 해당 위치가 퀸에게 공격받지 않는 유효한 위치인지 확인하고, 그 위치에 새로운 퀸을 방문하게 한 뒤, 다음 칸으로 또 이동하는 방식을 이용했다.
• 위 방식 그대로 했을 때 시간 초과가 나서 조금 의아했다. 이는 퀸이 좌우로의 이동이 가능하다는 점을 간과해서 발생했는데, 퀸을 둔 열에는 더는 퀸을 놓을 수 없기 때문에 굳이 그 부분에서까지 새로운 퀀을 방문시킬 필요가 없기 때문이다.
• 필자는 퀸이 방문 가능한 경우 다음 열로 바로 넘어가서 새로운 퀸을 위치시키는 방법으로 시간 초과를 해결했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Queue;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] dir;
    static boolean[][] visited;
    static int N;
    static int total ;

    public static void main(String[] args) throws IOException {

        N = Integer.parseInt(br.readLine());
        visited = new boolean[N][N];
        dir = new int[][]{{1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
        total = 0;

        btc(0, 0, 0);
        System.out.println(total);

    }
    public static void btc(int r, int c, int tmp){
        if(tmp == N){
            total += 1;
            return;
        }

        for(int i = 0 ; i < N ; i ++){
            if(isVal(r, i)){
                visited[r][i] = true;
                btc(r + 1, i, tmp + 1);
                visited[r][i] = false;
            }
        }
    }
    public static boolean isVal(int r, int c){

        for(int i = 0 ; i < N ; i ++){
            // 위 아래 확인
            if(visited[r][i] || visited[i][c]){
                return false;
            }
        }
        for(int j = 0 ; j < 4 ; j ++){
            // 대각선 확인
            int drow = r + dir[j][0];
            int dcol = c + dir[j][1];
            while(inRange(drow, dcol)){
                if(visited[drow][dcol]){
                    //true 인 경우
                    return false;
                }
                drow += dir[j][0];
                dcol += dir[j][1];
            }
        }
        return true;
    }
    public static boolean inRange(int r, int c){
        return r >= 0 && r < N && c >= 0 && c < N;
    }

}

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