[BOJ 9663] N-Queen (G4)

📍 문제 

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

 

📍 문제 풀이 

 

1. 2차원 배열 이용

처음에 문제를 보자마자 엥? 했던 부분은 퀸은 어떻게 움직이는데...?라고 하면서 풀이를 조금 찾아봤다

퀸은 상하좌우 일직선으로 움직일 수 있다.

 

 

 

첫번째 열부터 순차적으로 퀸을 배치한다. 

2차원 배열을 이용해서 위치를 이동하며 퀸을 배치할 수 있는지 확인한다

 

`isValid` 메서드를 이용해서 확인해야하는 경우의 수

1. 해당 열에 퀸이 존재하는지
2. 윗 대각선에 퀸이 존재하는지
3. 아랫 대각선에 퀸이 존재하는지

위의 경우를 모두 만족하지 않아야만 현재 위치에 퀸을 배치할 수 있다.

 

현재 위치에 배치할 수 있다면 배열의 값을 `1`로 두고 백트래킹을 통해 마지막까지 탐색한다.

import java.io.IOException;
import java.util.Scanner;

public class boj_9663 {
	static int n;
	static int result;
	static int[][] maps;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();

		maps = new int[n][n];

		backTracking(0);
		System.out.println(result);
	}

	static void backTracking(int cnt) {
		if (cnt == n) {
			result++;
			return;
		}

		for (int i = 0; i < n; i++) {
			if (isValid(cnt, i)) {
				maps[cnt][i] = 1;
				backTracking(cnt + 1);
				maps[cnt][i] = 0;
			}
		}
	}

	static boolean isValid(int x, int y) {
		for (int i = 0; i < x; i++) {
			// 현재 열에 퀸이 존재하는지 확인
			if (maps[i][y] == 1) {
				return false;
			}
		}

		for (int i = 1; i <= x; i++) {
			if (x >= i && y >= i && maps[x - i][y - i] == 1) {
				// 윗 대각선에 퀸이 존재하는지 확인
				return false;
			} else if (x >= i && y < n - i && maps[x - i][y + i] == 1) {
				// 아래 대각선에 퀸이 존재하는지 확인
				return false;
			}
		}
		return true;
	}
}

 

 

2. 1차원 배열 이용

2차원 배열을 이용하는 것과 다르게 1차원 배열을 이용해서 탐색할 수 있다.

2차원 배열의 경우에는 해당 위치에 퀸을 배치하였는지를 `maps[x][y]`의 값을 `0`과 `1`로 변경하며 확인하였지만,

1차원 배열의 경우에는 `queens[x]`의 값을 해당 열에 퀸이 위치하는 인덱스로 두어 확인할 수 있다.

int[] queens = {2,0,3,1};

 

위의 코드는 그림을 1차원 배열로 나타낸 경우다.

 

 

1차원 배열을 이용하여 구현한 전체 코드는 아래와 같다.

import java.io.IOException;
import java.util.Scanner;

public class Main {
	static int n;
	static int result;
	static int[] queens;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();

		queens = new int[n];

		backTracking(0);
		System.out.println(result);
	}

	static void backTracking(int cnt) {
		if (cnt == n) {
			result++;
			return;
		}

		for (int i = 0; i < n; i++) {
			queens[cnt] = i; // 배열의 값을 퀸이 존재하는 위치의 인덱스 값으로 할당
			if (isValid(cnt)) {
				backTracking(cnt + 1);
			}
		}
	}

	static boolean isValid(int col) {
		for (int i = 0; i < col; i++) {
			if (queens[col] == queens[i]) {	// 현재 열에 다른 퀸이 존재하는지
				return false;
			} else if (Math.abs(col - i) == Math.abs(queens[col] - queens[i])) { // 대각선에 퀸이 존재하는지
				return false;
			}
		}
		return true;
	}
}