백준 9663 N-Queen[Java]

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

풀이

백트래킹의 대표적인 문제다.
맨 첫번째 줄부터 하나씩 퀸을 놓은 다음, 그 다음 줄에 퀸을 놓는데 만약 퀸을 놓을 수 없는 자리면 그 칸은 더이상 탐색을 하지 않고 그 줄의 다음 칸에 퀸을 놓는다.

코드

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {

    static int n, m;
    static int[][] queen;
    static int answer = 0;

    static public boolean check(int row, int col) {
        for (int i = 1; i < row; i++) { //같은 열에 퀸이 있는 경우
            if (queen[i][col] == 1) {
                return false;
            }
        }
        for (int i = row-1, j = col-1; i > 0 && j > 0; i--, j--) { //현재 놓은 위치에 대각선에 퀸이 있는 경우
            if (queen[i][j] == 1) {
                return false;
            }
        }
        for (int i = row-1, j = col + 1; i > 0 && j <= n; i--, j++) { //현재 놓은 위치에 대각선에 퀸이 있는 경우
            if (queen[i][j] == 1)
                return false;
        }
        return true;
    }

    static public void nQueen(int row) {
        if (row > n) {
            answer++;
            return;
        }

        for (int i = 1; i <= n; i++) {
            queen[row][i] = 1;
            if (check(row, i)) {
                nQueen(row + 1);
            }
            queen[row][i] = 0;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        queen = new int[n+1][n+1];

        nQueen(1);

        System.out.println(answer);
    }
}

• check 함수를 통해 현재 칸에 퀸을 놓을 수 있는지 체크한다. 만약 놓을 수 있으면 nQueen(row + 1)을 호출하여 다음 줄에 퀸을 놓는다.
• row > n이라면, 모든 줄에 퀸을 놓은 것이므로, answer++한다.

---

다른 풀이

• 2차원 배열이 아닌 1차원 배열을 사용한다. 각 원소의 index를 '열'이라 생각하고, 원소 값을 '행'이라 생각하는 것이다.
• depth는 각 줄을 의미하고, 0부터 시작한다.
• depth == N이면 count++한다.
• check 함수로 퀸이 같은 줄에 놓여있는지, 대각선 위치에 있는지 확인한다.
  • arr[col] == arr[i]
  • Math.abs(col - i) == Math.abs(arr[col] - arr[i])

import java.util.*;

public class Main {
		
	static int N;
	static int[] arr;
	static int count = 0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		arr = new int[N];
		
		N_queen(0);
		
		System.out.println(count);
	}
	
	static void N_queen(int depth) {
		
		if(depth == N) {
			count++;
			return;
		}
		
		
		for(int i = 0; i < N; i ++) {
			arr[depth] = i;
			
			if(check(depth) == true) {
				N_queen(depth + 1);
			}
		}
	}
	
	static boolean check(int col) {
		
		for(int i = 0; i < col; i ++) {
			
			if(arr[col] == arr[i]) {
				return false;
				
			}else if(Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
				return false;
			}
		}
		
		return true;
	}

}

참고: https://st-lab.tistory.com/118
https://velog.io/@ilil1/%EB%B0%B1%EC%A4%80-9663%EB%B2%88-java