백준 9663번 N-Queen

N-Queen 문제

문제 정의

N-Queen 문제는 N x N 체스판에 N개의 퀸을 배치하는 문제로, 다음과 같은 조건을 만족해야 한다:

• 각 퀸은 같은 행, 같은 열, 또는 대각선에 다른 퀸이 없어야 한다.

문제 이해를 위해 N이 4인 경우에 탐색하는 과정의 일부를 보자

나는 이 문제를 보고 백트래킹 방식으로 접근해보았다.

코드는 다음과 같다.

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

public class Main {
    static int N, cnt;
    static int[][] board;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        board = new int[N][N];
        cnt = 0;

        nqueen(0);

        System.out.println(cnt);
    }

    private static void nqueen(int row) {
        if (row == N) {
            cnt++;
            return;
        }

        for (int col = 0; col < N; col++) {
            board[row][col] = 1;
            if (isValid(row, col)) {
                nqueen(row + 1);
            }
            board[row][col] = 0;
        }
    }

    private static boolean isValid(int row, int col) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 1) {
                    if (j == col || Math.abs(i - row) == Math.abs(j - col)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

제출 결과는 다음과 같다.

이후 N-Queen 문제를 일차원 배열만 사용해도 풀 수 있다는 것을 알게되었는데,

일차원 배열의 인덱스를 행으로, 안의 값을 열로 생각하고 푸는 것이다.

일차원 배열 안의 값이 같다면 Queen이 같은 열에 배치되어있는 것이고

행 번호의 차이와 열 번호 차이가 같다면 Queen이 대각선상에 있는 것이다.

이를 적용해서 다시 풀어보았다.

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

public class Main {
    static int N,cnt, board[];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        board = new int[N]; // 일차원 배열 사용
        cnt = 0;

        nqueen(0);

        System.out.println(cnt);
    }

    private static void nqueen(int row) {
        if (notAvailable(row-1)){ // 퀸을 배치하기 전에 이 행에 놓을 수 있는지 체크하여 가지치기하기
            return;
        }
        if (row == N) {
            cnt++;
            return;
        }
        for (int i = 0; i < N; i++) {
            board[row] = i;
            nqueen(row+1);
        }
    }

    private static boolean notAvailable(int RowNo) {
        for (int i = 0; i < RowNo; i++) {
            if (board[i] == board[RowNo] || Math.abs(board[i] - board[RowNo]) == RowNo - i){
                return true;
            }
        }
        return false;
    }

}

제출 결과를 보면 메모리 사용량과 시간이 크게 줄어든 것을 볼 수 있다.

---

참고 문헌

• https://chanhuiseok.github.io/posts/baek-1/
• https://frombasics.tistory.com/287