[JAVA] 백준 9663 N-Queen

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

 

문제분석

N*N 좌표평면에 퀸을 N개 서로 죽일 수 없게끔 놓는 경우의 수를 찾는, 대표적인 백트래킹 문제이다. 

처음에는 ArrayDeqeue를 활용한 stack DFS를 구현하였지만, 백준의 메모리 한도 때문에 메모리 초과로 자꾸 틀렸다. 따라서 stack DFS가 아닌 재귀(recursion) DFS를 활용하여 문제를 해결하였다.

 

또한, recursion DFS에서는 array[index]=value;구조를 활용하여, index에 row Index를, value에 col Index를 저장하는 방식을 사용하였다. 어차피 N * N 좌표평면이므로 array를 초기화할 때 N으로 초기화하면, arrayOutOfIndex와 같은 오류가 뜨지 않을 것 이라 생각했다.

 

 막상 코드를 짜보니, recursion방식이 Stack 방식에 비해 구조가 간단하다는 것을 느꼈다. 두 방법 다 활용할 줄 알아야 하는 것 같다.

코드

recursion DFS

import java.io.*;

public class Main {
    static int N;
    static int result = 0;
    static int[] col; // col[i] = i행의 퀸이 놓인 열 위치

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        col = new int[N];// col[i]=j 는 i행 j열에 퀸이 있다는 뜻

        backtrack(0); // 0번째 행부터 시작
        System.out.println(result);
    }

    // depth: 현재 행
    static void backtrack(int depth) {
        if(depth==N){
            result++;
            return;
        }
        for(int i = 0; i<N; i++){
            col[depth]=i;
            if(isValid(depth)){
                backtrack(depth+1);
            }
        }
    }

    // 퀸을 놓을 수 있는 자리인지 검사
    static boolean isValid(int row) {
        for(int i=0;i<row;i++){
            if(col[i]==col[row])return false;
            if(Math.abs(col[i]-col[row])==Math.abs(row-i))return false;
        }return true;
    }
}

 

stack DFS - 메모리 초과

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        int[] qList = new int[N]; //row * 15 + col 값 저장
        Arrays.fill(qList,-1);
        int count = 0;
        ArrayDeque<Integer> stack = new ArrayDeque<>(); // row * 15 + col 값 저장

        stack.push(0*15+0);
        
        while(!stack.isEmpty()){
            int temp = stack.pop();
            int row = temp / 15;
            int col = temp % 15;

            if(col >= N) continue; // col이 범위를 벗어나면 버림
            if(col+1<N)stack.push(row*15+col+1);

            // 대각선 혹은 같은 행에 Queen이 존재하는지 
            boolean flag = false;
            for (int i = 0; i < row; i++) {
                int qRow = i;
                int qCol = qList[i] % 15;
                if (qCol == col || Math.abs(qCol - col) == (row - qRow)) {
                    flag = true;
                    break;
                }
            }
            if(flag){
                continue;
            }else{  // 배치 가능한 경우
                if(row == N-1){
                    count++;
                }else{
                    qList[row] = row * 15 + col;
                    stack.push((row+1)*15+0);
                }
            }
        }
        bw.write(String.valueOf(count));
        bw.newLine();
        bw.flush();
        bw.close();

    }
}