[Java] 백준 9663 - N-Queen

Baekjoon_9663 - N-Queen

문제

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

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

입력

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

출력

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

---

해결방법

• N x N 체스판위에 퀸 N개를 공격할 수 없게 놓으려면 반드시 한 줄에 하나의 퀸만 있어야 한다는 의미가 된다.
  • 따라서 제일 첫 번째 줄부터 N 번째 줄까지 퀸을 하나씩 놓으며 공격 가능한 위치를 표시한다.
  • 그렇다면 다음 퀸은 반드시 공격 가능 위치가 표시되지 않는 곳에 놓아야 할 것이다.
  • 그렇게 N개의 퀸을 모두 놓았다면, 직전단계로 돌아가 다른 가능한 자리를 찾아보는 방법인 DFS로 구현한다.
• checkAttackablePos(x, y) 는 퀸이 (x, y) 지점에 놓였을 때 공격가능한 지점을 boolean 타입의 canAttack 배열에 표시하는 함수이다.
  • 이 때 첫 줄부터 차례로 퀸을 놓을 것이므로, x 보다 큰 행에만(방금 놓은 퀸보다 아래쪽 영역) 표시를 할 것이다.
• dfs(k) 메서드
  • k가 n이 되면 cnt++하며 탈출하는 재귀함수이다.
  • k 번째줄을 돌며 canAttack 배열이 false인 부분에 퀸을 놓고(board[k][i] = 1) 공격 범위를 표시한다. 그리고 dfs(k + 1)을 호출하며 다음줄로 넘어간다.
  • 초기화 하는 부분에서는
    • board[k][i] = 0으로 방금 놓은 퀸을 빼고
    • 이중 for문을 이용해 canAttack 배열을 초기화 한 후
    • 이중 for문을 이용해 남은 퀸들에 대해 공격범위를 다시 표시해준다.

코드

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

public class Baekjoon_9663 {
    static int n;
    static int[][] board;
    static boolean[][] canAttack;
    static int cnt = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        canAttack = new boolean[n][n];

        dfs(0);
        System.out.println(cnt);

    }

    public static void dfs(int k){
        if(k == n){
            cnt++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if(!canAttack[k][i]){
                canAttack[k][i] = true;
                board[k][i] = 1;

                checkAttackablePos(k,i);

                dfs(k + 1);

              	// 방금 놓은 퀸 빼기
                board[k][i] = 0;
              
              	// canAttack 배열 초기화
              	for (int j = 0; j < n; j++) {
                    for (int l = 0; l < n; l++) {
                        canAttack[j][l] = false;
                    }
                }

              	// 남은 퀸들의 공격범위 표시
                for (int j = 0; j < n; j++) {
                    for (int l = 0; l < n; l++) {
                        if(board[j][l] == 1){
                            checkAttackablePos(j, l);
                        }
                    }
                }
            }
        }
    }

    public static void checkAttackablePos(int x, int y){
      	// 퀸의 공격범위 표시
      
      	// 아래범위
        for (int i = x; i < n; i++) {
            canAttack[i][y] = true;
        }

        int posX = x;
        int posY = y;

      	// 대각선 왼쪽 범위
        while(true) {
            if(posX < 0 || posY < 0 || posX >= n || posY >= n){
                break;
            }
            canAttack[posX++][posY--] = true;
        }

      	// 대각선 오른쪽 범위
        while(true){
            if(x < 0 || y < 0 || x >= n || y >= n){
                break;
            }
            canAttack[x++][y++] = true;
        }
    }
}

이 문제를 푸는 도중 메모리에 관해 궁금증이 생겨서 자바의 메모리와 GC에 대해 공부를 해봤다.

• TroubleShooting - 객체 초기화시 메모리 사용량의 차이
• Java - JVM과 메모리 구조
• Java - Garbage Collector (GC)