[BackTracking] java boj 9663 N-Queen (자바)

N-Queen 성공

 

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

10 초

128 MB

43369

22847

14943

52.037%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

8

예제 출력 1 복사

92

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

9663번: N-Queen

 

내 체감 진짜 어려웠던 문제...

백트레킹의 바이블 같은 문제라고 한다.. (어려워)

 

처음 시도

처음에는 퀸의 이동방향에 맞춰 위치가 선정된 퀸이 이동할 수 있는 모든 방향을 방문처리하는 방향으로 풀었다.

1. 퀀은 현재 위치로 부터 가로,세로,대각선 방향으로 이동 가능

2. Invisit() 과 outVisit()을 만들어 방문처리

3. 연산도 많고, 제대로 된 체크가 되지 않아서 갈아 엎음... ㅠ

---

두번 째 시도

천천히 다시 생각해보고, 구글의 도움도 조금 받았다...ㅎㅎ (https://fbtmdwhd33.tistory.com/40 감사합니다ㅠ)

구글링을 통해 아래의 사진을 발견했는데, 사진을 보면서 이야기 하자면

사진 출처 : https://fbtmdwhd33.tistory.com/40

N*N 배열에 N개의 퀸이 존재해야하는 경우의 수이고, 같은 열, 같은 행에 존재하지 않아야한다. (대각선은 나중에)

즉, 각 행 당 한개의 퀸이 존재하고, 존재하는 퀸들의 열이 중복되지 않은 상태에서 -> 대각선의 존재 유무를 파악한다.

 

1. 퀸의 위치를 저장할 1차원 배열을 정의한다. [ queen[행] = 열 ]

2, 0번 행부터~ n-1행까지 백트래킹의 인자로 들어간다. (순서대로)

3. 각 행에 들어가는 열값을 순서대로 모든 경우의 수(N개)를 조회한다.

4. 퀸의 위치를 정하고, 정한 퀸의 위치가 존재할 수 있는 위치인지 파악한다.

5. 파악하는 방법은

1. 현재 행을 기준으로 이전 행들만을 비교 (시간 단축을 위해)
2. 이전 행들의 열값과 현재 행의 열 값 비교
3. 이전 행에 위치한 퀸들의 대각선에 현재 퀸의 위치가 존재하는지 파악 [ 이전행 - 현재행 == 이전 열 - 현재 열]
4. Math.abs()로 왼쪽 대각선, 오른쪽 대각선 둘 다 비교 가능

 

혹시 누군가에게 도움이 될 수도 있는.. 내 자연어(?) 정리..

 

package BackTracking;

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

public class boj9663_NQueen {
	static int n;
	static int map[][];
	static boolean visit[][];
	static int result = 0;

	static int queen[]; // queen[행] = 열

	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];
		
//		Arrays.fill(queen, -18);
		backTracking(0);

		System.out.println(result);
	}

	// idx : 행
	private static void backTracking(int idx) {
		// 탈출 조건
		if (idx == n ) {
			result++;
			return;
		}

		// i : 열값
		for (int i = 0; i < n; i++) {
			// 첫 행 (비교 x)
			queen[idx] = i;
			// check true면 다음 행으로/ 퀸을 놓을 수 없으면 다음 열값을 저장해서 확인
			if (idx == 0 || check(idx))
				backTracking(idx + 1);

		}
	}

	public static boolean check(int check) {
		for (int j = 0; j < check; j++) {
			// queen[j(행)] : 열값 == queen[check(현재 행)] : 열값
			// j- check(행 거리) == 열거리 -> 대각선 상에 존재
			if (queen[j] == queen[check] ||check - j == Math.abs(queen[j] - queen[check]))
				return false;
		}

		return true;
	}

}