[백준 알고리즘] 9663번 자바(Java) N-Queen

조건

문제

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

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

 

입력

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

출력

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

 

풀이

퀸은 직선과 대각선으로 이동할수있기때문에 한행에 한개만 존재가능하다. 아래처럼 말이다.
따라서 첫행부터 한행씩 내려가면서 찾는 DFS를 생각을 했다. 

따라서 visted[N][N]을 통해 공격가능한곳과 이미 퀸이 놓인자리를 방문 처리할려고 한다. 시간복잡도 상으로는

한행이 진행될때마 한열씩 접근을 못하기때문에 15! 시간복잡도라고 생각을했다. 근데 추가적으로 대각선도 생각을 하면 
15!(13억)보다는 훨씬 낮은 시간복잡도가 나오게 된다. 그러면 10초(10억)안에는 통과할수있다.

이 문제는 사실 행내려가서면서 빈칸에 퀸을 놓고 공격범위를 표시하는것보다 중요한것은 
dfs로 끝 index에 도달한후에 다시 돌아올때 공격범위 회수를 하는부분이다. 왜냐면 전 퀸의 공격범위에 들어온곳이
현재 퀸의 공격범위에 들어오게되면 다시 공격을 회수할때 그부분을 체크를 못하는 오류가 생길수있다.

 

그래서 내가 생각한 방법은 visited를 boolean이 아닌 byte형으로 지정해 0은 방문x, 1은 방문ㅇ, 2>중첩방문이 되는식으로 진행을 했다. 메모리적으로도 생각을 해봤을때 byte[][] visited = new byte[15][15]; 는 15x15x1byte 225byte밖에 차지를 안한다. boolean도 결국 컴퓨터가 처리하는 최소 메모리단위가 1byte기때문에 같은것을 알 수 있다. 

그래서 위에 과정을 그림으로 표현하면 다음과 같다.(참고로 다른분들의 풀이랑은 조금 다를수있어 제 풀이는 참고만 하는게 좋을 것같다.) 

첫행에 퀸 넣어주기

두번째 행에 퀸 추가

세번째 행에 퀸 추가

이런식으로 진행을 해서 중첩되는곳은 visited[i][j]의 숫자가 1을 넘어가게된다. 이후에 끝 index까지 찍은후 다시 돌아올때
퀸을 없애면서 대각선경로와 하단직선경로에 visited[i][j]를 다 --해주면 원상태로 돌아온다.

 

세번째행의 퀸dfs끝난후 두번째행으로 돌아올때 visited-- 과정

그렇게 해서 이후에 세번째 행에 퀸이 생성될 수 있는 또다른 index가 있다면 방금의 과정을 반복하면 된다.

 

예제 입력 예시

8

 

예제 출력 예시

92

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//9663 N-Queen

public class Main {
    static int N;
    static byte[][] visited;       //방문x = 0, 방문하면 1, 중첩방문 >1
    static int cnt = 0;
    static int depth = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        visited = new byte[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                visited[i][j] = 0;
            }
        }

        for (int i = 0; i < N; i++) {  //첫행만 노드 값 정의해주고 이후에는 백트래킹
            dfs(0,i);
        }
        System.out.println(cnt);
    }

    static void dfs(int y, int x) {  //추후에 depth전역변수 설정후 메소드 파라미터에서 빼도됨
        //  System.out.println("node y:" + node.y + " x: " + node.x + " depth: " + depth);
        if (depth == N) {  //깊이가 같으면 마지막행 모든 칸들 확인하면서 방문안했으면 cnt++;
            cnt++;
            return;
        }
        else{
            //퀸의 이동경로 방문체크하기
            //아래방향
            for (int i = y+1; i < N; i++) {
                visited[i][x]++;
            }
            //좌하단 대각선
            int le = x-1;
            int down1 = y+1;
            while (0 <= le && down1 < N) {
                visited[down1++][le--]++;
            }
            //우하단 대각선
            int ri = x+1;
            int down2 = y+1;
            while (ri < N & down2 < N) {
                visited[down2++][ri++]++;
            }

            //다음행중에 이동경로 없고 방문안한 칸들로 이동
            for (int i = 0; i < N; i++) {
                if (visited[y + 1][i] == 0) {
                    visited[y + 1][i] = 1;
                    depth++;
                    dfs(y + 1, i);
                    depth--;
                    visited[y + 1][i] = 0;
                }
            }
            //퀸의 이동경로 다시 제거
            for (int i = y; i < N; i++) {
                visited[i][x]--;
            }
            //좌하단 대각선
            le = x;
            down1 = y;
            while (0 <= le && down1 < N) {
                visited[down1++][le--]--;
            }
            //우하단 대각선
            ri = x;
            down2 = y;
            while (ri < N & down2 < N) {
                visited[down2++][ri++]--;
            }
        }
    }
}

 

 

 

 

문제 출처

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

9663번: N-Queen