[코딩테스트] [9663] N - Queen

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

10 초

128 MB

137746

66952

42960

46.911%

문제

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

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

입력

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

출력

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

문제풀이

• 행렬에 퀸을 놓았을 때, 서로를 공격할 수 없는 상태가 되도록 배치하는 문제
• 퀸이 놓여있는 좌표에 직선과 대각선이 만들어지는 구간에 아무것도 없어야 한다.
• 1 ≤ N ≤ 15
• 전체 경우의 수를 출력하자.

문제 분석

• 퀸은 하나의 행에 하나만 존재할 수 있다. (가로 세로 줄을 공격할 수 있기 때문)
  • 재귀함수 탐색의 기준으로 사용할 수 있다.
• 마지막 행에 퀸 배치를 성공하면, 유망한 경우의 수가 하나 증가한다.
• 불가능한 경우는 탐색을 중단하여 가지치기 한다.

체스판의 표현

• 한 행에 1개의 퀸만 존재할 수 있다.
• 따라서 1차원 배열만으로 퀸의 위치를 표현할 수 있다.
• queen[행번호] = 열번호
• queen[2] = 3
  • 체스판의 2행 3열에 퀸을 배치할 수 있다.

BaseCase

• 재귀 함수가 마지막 행에 퀸을 배치한 경우
  • 0번째 행부터 순서대로 모든 경우의 수를 가지 치며 카운트

Recursive Case

• [0, n] 열을 돌아다니면서 퀸 배치를 시도한다

Backtrack

• 체스 룰에 위배되는 경우에는 퀸을 배치할 수 없도록 막는다.

public static boolean isVaild(int row, int col) {
	for (int i = 0; i < row; i++) {
		if (queen[i] == col) return false;
		if (Math.abs(i - row) == Math.abs(queen[i] - col)) return false;
	}
	return true;
 }
}	

전체코드

import java.util.*;

class Main {
    static int[] queen = new int[15]; // 최대 크기

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // N 입력
        System.out.print(solve(n, 0)); // 결과 출력
    }

    static int solve(int n, int row) {
        if (row == n) return 1; // 모든 행에 퀸을 배치한 경우

        int count = 0;
        for (int col = 0; col < n; col++) {
            if (isVaild(row, col)) {
                queen[row] = col; // 퀸 배치
                count += solve(n, row + 1); // 다음 행 탐색
            }
        }
        return count;
    }

    static boolean isVaild(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (queen[i] == col) return false;
            if (Math.abs(row - i) == Math.abs(queen[i] - col)) return false;
        }
        return true;
    }
}