백준 9663번 N-Queen(java)

[Gold IV] N-Queen - 9663

문제 링크

성능 요약

메모리: 15468 KB, 시간: 7328 ms

분류

백트래킹, 브루트포스 알고리즘

제출 일자

2024년 7월 23일 05:16:08

문제 설명

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

풀이

N*N 체스판 위에 퀸 N개를 서로 공격할 수 없게 두는 문제이다.

 

이 말은 퀸을 둘 때 퀸의 공격 범위 내에 다른 퀸이 존재하지 않는다면, 해당 칸에 퀸을 둘 수 있다는 얘기이다.

 

따라서 퀸의 공격 범위 내에 다른 퀸이 존재하는지 판단하는 함수를 하나 만든 후 dfs로 풀이하면 해결할 수 있다.

 

public static boolean ganung(int x, int y, int fcnt){
    for(int  i =0;i<fcnt;i++){
        if(y == yual[i]){
            return false;
        }
        if(Math.abs(yual[i] - y) == Math.abs(hang[i] - x)){
            return false;
        }

        if(hap[i] == x+y){
            return false;
        }
        if(hang[i] == x){
            return false;
        }
    }

    return true;
}

 

해당 x,y 위치에 퀸을 놓을 수 있는지 판단하는 함수는 다음과 같이 작성했다.

 

같은 열 또는 같은 행에 존재한다면 false를 반환, 대각선에 위치한다면 false를 반환하게 하였다.

 

왼쪽 위 대각선↖️과 오른쪽 아래 대각선 ↘️ 의 경우는 (퀸이 놓여진 위치의 x - 새로 퀸이 놓일 자리의 x)와 

(퀸이 놓여진 위치의 y - 새로 퀸이 놓일 자리의 y) 의 절대값이 같을 경우에 해당한다.

 

↗️↙️ 이 두 대각선의 경우엔,  기존 퀸이 놓여진 위치의 x+y 와 새로 놓일 자리의 x+y가 같을 경우 해당한다.

 

 

public static void dfs(int x, int y, int fcnt){
    if(fcnt == N){
        cnt++;
        return;
    }
    int iy = y;
    for(int jx = 0 ;jx <N;jx++){
        if(ganung(jx,iy,fcnt)){
            yual[fcnt] = iy;
            hap[fcnt] = iy + jx;
            hang[fcnt] = jx;
            dfs(jx,iy+1,fcnt+1);
        }
    }

}

 

dfs는 다음과 같이 만들었다. 퀸이 놓일 수 있는 자리라면 해당 위치에 퀸을 놓고 열과 행 그리고 합을 계산하여 저장시켜

후에 ganung 함수에서 퀸을 놓을 수 있는 위치인지 계산할 때 사용하도록 했다.

 

전체 코드 

package hello.core.backjoon;
import java.io.*;
import java.util.*;
import java.math.*;
import java.lang.*;

public class Main{
    static int N,cnt=0, yual[], hap[], hang[];
    static Boolean selec[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String num = br.readLine();
        N = Integer.parseInt(num);

        yual = new int[N];
        hap = new int[N];
        hang = new int[N];

        dfs(0,0,0);

        bw.write(String.valueOf(cnt));
        bw.flush();

    }

    public static void dfs(int x, int y, int fcnt){
        if(fcnt == N){
            cnt++;
            return;
        }
        int iy = y;
        for(int jx = 0 ;jx <N;jx++){
            if(ganung(jx,iy,fcnt)){
                yual[fcnt] = iy;
                hap[fcnt] = iy + jx;
                hang[fcnt] = jx;
                dfs(jx,iy+1,fcnt+1);
            }
        }

    }

    public static boolean ganung(int x, int y, int fcnt){
        for(int  i =0;i<fcnt;i++){
            if(y == yual[i]){
                return false;
            }
            if(Math.abs(yual[i] - y) == Math.abs(hang[i] - x)){
                return false;
            }

            if(hap[i] == x+y){
                return false;
            }
            if(hang[i] == x){
                return false;
            }
        }

        return true;
    }


}