[골드4] 9963. N-Queen (Java)

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

9663번: N-Queen

 빽트래킹,,뻨킹,,,

---

※  문제를 요약하면 아래와 같습니다.

▶ 빽트래킹의 대표 문제 중 하나인 N-Queen 문제

▶ 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓을 수 있는 경우의 수 찾기

▶ Input : 1 <= N < 15

▶ Output : 퀸 N개가 서로 공격할 수 없게 놓는 경우의 수

---

◈ Input

8

◈ Output

92

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 퀸을 N개 놓을 때 놓을 수 없는 공간은 전부 생략.

▶ 각 열 및 행에는 퀸이 하나만 존재 가능, 즉 각 열과 행에는 하나의 퀸만 존재

▶ 이를 트리 형태로 표현, dfs를 통해 경로가 아닌 경우, 전부 생략

 

▶ 차후, 추가 설명 작성 예정

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

	static int N;
	static int nQueenCount = 0;
	static int[] columnsBoard = new int[15];

	public static void NQueen(int nRow) throws IOException {
		if (nRow == N) {
			nQueenCount++;
			return;
		}

		for (int nCol = 0; nCol < N; nCol++) {
			// Use the array as a columnBoard
			columnsBoard[nRow] = nCol;
			
			boolean bCheck = true;
			// Check if the next queen are in diagonal
			// if it's in diagonal it'll have same subs with each cols and rows
			for (int j = 0; j < nRow; j++) {
				if (columnsBoard[nRow] == columnsBoard[j]
						|| nRow - j == Math.abs(columnsBoard[nRow] - columnsBoard[j])) {
					bCheck = false;
					break;
				}
			}
			
			if(bCheck)
				NQueen(nRow+1);

		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(bReader.readLine());

		N = Integer.parseInt(st.nextToken());

		NQueen(0);

		bWriter.write(nQueenCount + "\n");
		bWriter.flush();
		bWriter.close();

	}

}

힘들지만 재밌다!

읽어주셔서 감사합니다!

Good Luck! (피드백 감사합니다!)