[백준][JAVA알고리즘]9663번 풀이(N-Queen) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 9663번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 9663 (N-Queen)

문제

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

 

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

 

입력

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

 

출력

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

 

입력 예시

8

출력 예시

92

성공코드

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

public class Main {

	static int[] arr;
	static int N;
	static int de = 0;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		N = Integer.parseInt(str);
		
		arr = new int[N];
		
		dfs(0);
		System.out.println(de);
}
	public static void dfs(int depth) {
		
		if(depth == N) {
			de++;
			return;
		}
		
		for(int i = 0 ; i < N; i++) {
			arr[depth] = i;
			if(possible(depth)) {
				dfs(depth+1);
			}
		}	
	}
	
	public static boolean possible(int col) {
		
		for(int i = 0 ; i < col ; i++) {
		//행에 일치하는게 있는지 판별
		if(arr[i]==arr[col]) {
			return false;
		}
		//대각선에 일치하는게 있는지 판별
		else if(Math.abs(col-i) == Math.abs(arr[col]-arr[i])) {
			return false;
		}
			
		}
		
		return true;
	}
}

N-Queen문제는 백 트레킹 기법에서 대표적인 알고리즘 문제입니다. 그러나 저는 처음 접해봐서 어떠한 방식으로 접해야 될지 몰랐습니다. 항상 백 트레킹 기법을 사용해보려 할 때 가장 큰 문제점은 어떠한 수를 depth 즉 깊이로 두고 풀 것인가 하는 문제였습니다.

 

결과론적으로 해당 풀이에서의 depth는 행으로 잡았습니다. 해당 문제의 풀이를 설명하기에 앞서서 간략히 문제에 대해 설명하자면 다들 체스에서 퀸이 움직일 수 있는 위치가 무엇인지 알아야 합니다.

---

간단한 문제 이해

가로, 세로, 대각선의 방향으로 모두 이동할 수 있는 역할입니다. 해당 문제에서 묻고 있는 문제는 입력으로 8 이 주어지면 가로세로 8개의 체스판에서 8개 퀸을 놓을 수 있는 경우의 수를 묻고 있습니다. 예를 8*8 크기의 체스판에 8개의 퀸을 배치할 수 있는 경우의 수들로 볼 수 있습니다.

---

알고리즘 흐름도

입력받기 -> arr 설정하기 (arr은 각 인덱스가 각 행을 의미한다.) -> dfs 시작하기 -> 결과가 나올 때마다 de 더해주기 -> dfs가 끝날 시 de 출력하기

---

STEP1 arr 설정하기

해당 문제에서 체스판은 2차원 배열 같은데 왜 1차원을 사용하는지 이해하지 못하였지만, arr의 크기가 바로 행의 크기가 되고 각 인덱스에 있는 값이 바로 열을 의미하게 하면 된다는 간단한 생각의 전환을 이해해 볼 수 있었습니다.

 

예를 들어 arr []이라는 배열에 0 4 2 3이라는 값이 들어있다고 가정해 봅시다. 그렇다면,

*
			*
	*
		*

이런 식으로 체스판이 구성되어 있음을 보여줍니다.

 

arr = new int[N];

즉, 우리는 받은 입력의 크기만큼만 arr의 크기를 설정해주면 됩니다.

---

STEP2 dfs 설정하기 for

dfs문제의 가장 핵심인 바로 for을 구현하는 작업입니다. 이에 앞서서 dfs의 인자 값을 설정할 때 항상 depth를 시작으로 하나씩 더 늘려 가면 됩니다. 우선 가장 기본인 depth를 인자로 받아서 구현해보도록 하겠습니다.

 

for(int i = 0 ; i < N; i++) {
			arr[depth] = i;
			if(possible(depth)) {
				dfs(depth+1);
			}
		}

자, 저희는 항상 입력 예시로 생각해보면서 내려가면 됩니다. 인자 depth로 0이 들어왔다 가정해보면, arr [0]에 값이 0이 들어가게 됩니다. 이 의미는 무엇이냐, 바로 0번째 행에 0번 열에 값을 넣어준다는 의미!

 

그리고 possible이라는 함수를 만들어 해당 위치에 퀸을 위치해도 되는지 확인 작업을 거칩니다. (자세한 내용은 STEP 3을 확인해보세요) 만약 해당 함수에서 true가 반환되면, 위치가 적합하니 다음 행으로 이동하기 위해 depth에 +1을 해줍니다.

---

STEP 3 possible 설정하기

이제는 possible을 구현해봐야 합니다. 이때 저희가 고려해야 될 상황이 무엇인지 확인해야 합니다. 저희는 우선 for문에서 알 수 있는 점은 각행에는 하나의 값만 들어가진 다는 거! 왜냐하면 arr [depth] = i 이문장밖에 행에 넣을 수 있습니다. 즉 해당 체스판에서 행 부분에 한 개의 값 만들어가게 되죠.

 

그렇게 된다면 저희가 possible에서 고려해 줘야 하는 것은 바로 같은 열과 대각선에 있는지 없는지만 판별해주면 됩니다.

	public static boolean possible(int col) {
		
		for(int i = 0 ; i < col ; i++) {
		//열에 일치하는게 있는지 판별
		if(arr[i]==arr[col]) {
			return false;
		}
		//대각선에 일치하는게 있는지 판별
		else if(Math.abs(col-i) == Math.abs(arr[col]-arr[i])) {
			return false;
		}
			
		}
		
		return true;
	}

해당 값으로 depth가 들어옵니다. 이 depth는 앞서 for문에서 행의 위치를 의미했었죠. 예를 들어 col에 4라는 값이 들어왔다고 생각해봅시다.

그렇게 되면, arr [0] ~ arr [3]까지의 값 중에서 arr [4]와 같은 값이 있으면, false를 반환하라고 나와있죠.

즉 0, 1, 2, 3번째 행에서 value 값은 열을 의미하겠죠? 즉 같은 열에 있는 값들이 있으면, false를 반환해야죠!

 

그다음 else if 바로 대각선을 판별해주는 것 무엇을 의미하는지를 알아야 합니다. Math.abs(col-i)는 무엇을 의미할까요. 이전 예시로 계속 가보죠. col=4라면 i는 0 ~ 3의 숫자가 순차적으로 들어가겠죠. 하나씩 계산해보죠

계산에 앞서서 arr이 이렇게 구성되어있다고 가정해보죠

*
			*
	*
		*
				*

arr = {0,4,2,3,5} 이런 식으로 들어있다고요!

Math.abs(4-0) = Math.abs(arr [4]-arr [0]) => 4 == Math.abs(5 - 1) => 4==4

자 그러면 0번 하여과 4번 하아에서 대각선에 있는 값이면 해당 식이 만족할 수밖에 없게 됩니다.

 

즉 간단해요 대각선에 있다는 것을 알 수 있으려면 해당 표에서 행과 열을 뺀 절댓값이 같은 값이면 됩니다. 궁금하신 분은 2번 하여과 3 번행이 대각선에 위치하는 것을 알 수 있는데 3번 하아의 경우 2번째 행 - 1번째 열 = 1

3번 하아의 경우 3번째 행 - 2번 재열 = 1이 나오는 것을 알 수 있죠. 다른 방법으로는 각각의 열과 행을 빼주어도 같은 값이 나오게 됩니다. 이처럼 대각선을 판별하는 여러 가지 방법을 이용해볼 수 있죠

---

STEP 4 dfs 설정하기 if

 뭐... if는 가장 간단합니다. depth가 N과 같아지게 되면 즉, N개의 퀸이 다 배열되었다는 것을 의미합니다. 왜냐하면 앞서 for 설정하기에서 if문이 통과해야 depth가 1이 커집니다. 해당 식을 통과하지 못한다면, 그냥 for문이 끝나버려, 해당 dfs는 종료되게 되죠. 즉, depth와 N이 같아지는 시기는 모든 퀸이 모두 배열되었다는 것을 의미합니다. 그렇다면, 이제 저희는 정답에 +1을 해주면 끝!

if(depth == N) {
			de++;
			return;
		}

---

해당 알고리즘을 풀면서 저도 많이 헤매면서 다른 분들의 코드를 참고하며 이해했습니다. 백 트레킹 기법 알고리즘에서 항상 depth를 어떻게 설정해야 할지 잘 생각해봐야 하는 문제인 거 같습니다.