[백준] 9663번 N-Queen

1) 생각

체스판에 N개의 Queen을 겹치지 않는 범위로 놓을 수 있는가에 관한 문제이다.

백 트래킹이라하는 알고리즘의 대표적인 문제로 볼 수 있다. 모든 경우의 수를 따져보면서 중간에 아니다 싶으면 백 해서 다시 맞나 살펴보는 형태의 알고리즘이다. 따라서 해당 경로를 방문 표시 할 수 있는 배열을 만들어 주었다.

NxN 크기의 배열을 만들어서 진행을 하였는데 다른 풀이들을 보니 1차 배열로도 문제를 풀 수 있는것 같다. 이경우는 좀 더 빠르게 문제를 해결할 수 있을 것이다.

2) 방안

백트래킹을 하며 Queen을 한 줄에 하나씩 놔보면서 진행한다.

import java.io.IOException;
import java.util.Scanner;
 
public class Main{
    static int n;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        visited = new boolean[n][n];
        solve(0);
        System.out.println(result);
    }
    
    static boolean visited[][];
    static int result;
    private static void solve(int x) {
        if(x==n) {
            result++;
            return;
        }
        for(int i=0;i<n;i++) {
            if(!check(x,i)) continue;
            visited[x][i] = true;
            solve(x+1);
            visited[x][i] = false;
        }
    }
    
    private static boolean check(int x,int y) {
        // 위로
        for(int i=x;i>=0;i--)
            if(visited[i][y]) return false;
        // 왼쪽 위로 대각선
        int tx = x-1;
        int ty = y-1;
        while(tx>=0&&ty>=0)
            if(visited[tx--][ty--]) return false;
        // 오른쪽 위로 대각선
        tx = x-1;
        ty = y+1;
        while(tx>=0&&ty<n)
            if(visited[tx--][ty++]) return false;
        return true;
    }
}