[백준] N-Queen 👑 (Java)

⏳문제

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

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

입력

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

출력

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

예제 입력

8

예제 출력

92

---

✏️풀이

이 문제는 대표적인 백트래킹(BackTracking)문제입니다.
문제 이해를 위해 조금 더 설명하자면,
퀸은 체스에서 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있습니다.

예를 들어, 8 x 8 체스판이 입력으로 주어진다면, 이 문제의 solution 중 한 가지는 아래 그림과 같습니다.

이 경우 규칙에 의해 배치된 8개의 퀸은 서로 공격할 수 있는 경우의 수가 하나도 없습니다.
이 문제는 이러한 경우의 수를 모두 구하는 것입니다.
따라서 DFS를 사용해 모든 경우의 수를 고려하면 문제를 해결할 수 있습니다.

예를 들어 N이 4인 경우, 0번 행에 놓는 퀸의 위치는 이렇게 4가지입니다.

만약 첫 번째를 거쳐 두 번째 경우에서 DFS 탐색을 하는 경우라면, 1번 행에 퀸을 배치하는 4가지 경우의 수로 분기가 될 것입니다.
하지만, 첫 번째 ~ 세 번째 경우에는 그 전 행에 배치시켜 놓았던 퀸에게 공격을 받을 수 있는 상황입니다. 이 경우들은 절대 solution이 될 수 없기 때문에 더 이상 탐색을 진행하지 않도록 합니다.
따라서 네 번째 경우에만 계속해서 탐색을 진행하도록 해야 합니다.

이렇듯, 규칙에 따라 퀸을 배치할 수 없는 경우를 만났을 경우에는 더 이상 탐색하지 않도록 종료 조건을 잘 세워주어야 보다 효율적으로 탐색할 수 있습니다.
이제 구현을 해 보도록 하겠습니다.

주요 변수

static int[] arr;
static int sum;

arr 배열은 각 행에 퀸이 놓인 열의 인덱스를 저장합니다.
예를 들어, arr[0]은 첫 번째 행에 퀸이 놓인 열을 나타냅니다.
sum 변수는 퀸을 배치하는 방법의 수를 세기 위해 사용했습니다.

메인 메서드

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    
        int n = sc.nextInt();
        arr = new int[n];
        dfs(0, n);
        System.out.println(sum);

        sc.close();
    }

Scanner를 통해 n을 입력받고, 해당 크기 만큼 arr 배열을 생성해 줍니다. 그리고 dfs 메서드를 호출해 탐색을 시작하는데, 파라미터로 현재 행과 체스판의 크기 n을 보내주도록 합니다.

DFS 메서드

	public static void dfs(int start, int n) {
		// 종료 조건 : 모든 행에 퀸을 성공적으로 배치했다면
		if (start == n) {
			sum += 1;
			return;
		}
		
		for (int i = 0; i < n; i++) {
			boolean check = true; // 현재 열에 퀸을 놓을 수 있는 지에 대한 여부
			for (int j = 0; j < start; j++) {
				// 같은 열에 퀸이 있는 지
				// 왼쪽 방향 대각선에 퀸이 있는 지
				// 오른쪽 방향 대각선에 퀸이 있는 지
				if (arr[j] == i || arr[j] + (start - j) == i || arr[j] - (start - j) == i) {
					check = false;
					break;
				}
			}
			
			if (check) {
				arr[start] = i;
				dfs(start + 1, n);
			}
		}
	}

우선, 종료 조건을 먼저 세워 주었습니다.
탐색이 종료되었다는 것은 n행까지 탐색을 했다는 의미이고, n행까지 탐색을 했다는 의미는 solution(퀸을 공격받지 않는 위치에 모두 배치한 경우)을 발견한 경우이기 때문에, sum에 1을 더하고 탐색을 종료합니다.

종료 조건을 세웠으니 이제 탐색하는 경우를 고려해 보겠습니다.
우선, 현재 행(start)에서 퀸을 배치할 수 있는 경우의 수는 총 n가지 입니다.
그리고, 현재 행(start)보다 앞에 배치했던 퀸들의 위치를 파악해야 하기 때문에, 반복문을 사용해 이전 행에 대한 위치 j를 설정해 줍니다.

이제 3가지 조건을 따져서 현재 위치에 퀸을 배치할 수 있는 지 확인해 보겠습니다.

• arr[j] == i : 같은 열에 퀸이 있는 지 확인
• arr[j] + (start - j) == i : 왼쪽 대각선으로부터 공격받을 수 있는 지 확인
• arr[j] - (start - j) == i : 오른쪽 대각선으로부터 공격받을 수 있는 지 확인

이 세 가지 조건 중 하나라도 참이면, 해당 위치에는 퀸을 놓을 수 없고, 모두 해당하지 않는다면, 해당 위치에 퀸을 놓을 수 있기 때문에, arr배열에 해당 열의 위치 i를 저장하고, 재귀를 통해 탐색을 이어나도록 해 줍니다.

최종적으로 start가 n까지 다다른 모든 경우의 수가 sum에 저장되고, 구하고자 하는 solution의 개수가 됩니다.

👾전체 코드

import java.util.*;

public class SWEA_2806 {
	static int[] arr; // 각 행에 퀸이 놓인 열의 인덱스 저장
	static int sum; // 퀸을 배치하는 방법의 수
	
	public static void dfs(int start, int n) {
		// 종료 조건 : 모든 행에 퀸을 성공적으로 배치했다면
		if (start == n) {
			sum += 1;
			return;
		}
		
		for (int i = 0; i < n; i++) {
			boolean check = true; // 현재 열에 퀸을 놓을 수 있는 지에 대한 여부
			for (int j = 0; j < start; j++) {
				// 같은 열에 퀸이 있는 지
				// 왼쪽 방향 대각선에 퀸이 있는 지
				// 오른쪽 방향 대각선에 퀸이 있는 지
				if (arr[j] == i || arr[j] + (start - j) == i || arr[j] - (start - j) == i) {
					check = false;
					break;
				}
			}
			
			if (check) {
				arr[start] = i;
				dfs(start + 1, n);
			}
		}
	}
	
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++)
		{
			int n = sc.nextInt();
			sum = 0;
			arr = new int[n];
			
			dfs(0,n);
			System.out.println("#" + test_case + " " + sum);

		}
		sc.close();
	}
}

---

🔗문제 링크
💻Repository