[알고리즘] N-Queen (백트래킹)

백트래킹이란 dfs문제에서 깊이를 탐색하다가 요쪽(?)으로 계속가면 원하는 값을 얻지 못함을 미리 깨닫고 더이상 들어가지 않는 기법이다. 일명 가지치기라고 한다. dfs의 단점은 무한 반복될 수 있는 구간에서는 빠져나올 수 없다는 단점이 있다. 이를 적절하게 해결할 수 있는 하나의 기법이 되고, 그 외에 bfs를 통해서 빠르게 탐색하는 방법도 있지만 bfs는 인덱스가 진행될 수 록 메모리가 지수승으로 폭발 증가한다는 단점이 있다. 그래서 적절하게 dfs를 활용해서 앞서 미리 이 가지가 유효할지를 검사하여 잘라낼지 진행할지를 결정한다.

 

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

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

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

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

 

백트래킹 문제중 가장 유명하고 적절한 예제로 볼 수 있는 N-Queen 문제이다. 체스에서 퀸은 강력하면서도 조심히 써야하는 말인데 체스판에서 행과 열, 대각선을 모두 마음대로(?) 이동할 수 있다. 만약 다른 어떤 말이 잡히지 않기 위해서는 이 퀸의 행과 열, 그리고 대각선에 존재해서는 안된다. 

 

이 퀸의 특성을 이용한 문제이다! n개의 퀸을 N x N 체스 판에 서로 잡히지 않게 (물론 1턴기준) 배치하는 문제이다. 여기서 백트래킹을 어떻게 활용할 수 있을까?

 

 

 

먼저 가장 기본적으로 당연하게도! n개의 퀸 중에서 첫 번째 퀸을 먼저 둬야한다. 그리고 그 퀸을 기준으로 다음 퀸을 두면 된다. 이게 가장 기본이다. 근데 다음 퀸을 둘 떼, 둘 수 있는지 없는지를 판단하는 기준이 있어야 한다. 그것은 우리가 앞전에 둔 퀸의 위치와 같은 행, 열에 존재하거나 대각선에 존재하면 문제가 원하는 답과 달라지기 때문에 이 구간을 기준으로 둬야한다.

 

그럼 여기서 백트래킹 기법을 사용할 수 있다. 첫 번째 퀸을 두고 다음 퀸을 두는데 첫번째 퀸의 행 열 대각선에 두번째 퀸을 놓는다면 앞으로 더 이상 가지를 깊게 판단할 이유가 있을까? 답은 없다이다. 왜냐면 이미 첫번재 퀸의 행 열 대각선에 두번째 퀸을 둔다는 것 자체가 이미 서로 잡을 수 있는 배치가 되어버리기 때문에 판단기준에서 제외시켜버리는 것이다. 만약 이 기법을 사용하지 않는다면 되지도 않는 경우를 모두 판별하기 때문에 시간이 엄청나게 걸릴 것이다.

 

코드를 보자

 

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

public class BaekJoon_15_9663 {
	private static BufferedReader reader;
	private static BufferedWriter writer;
	private static int n, count;
	private static int[] col;

	private static void dfs(int row) {
		if (row == n) { // n열까지 검사 완료되면 성공 (끝자락이므로)
			count++;
		} else {
			for (int i = 1; i <= n; i++) {
				col[row + 1] = i; // 다음 행의 1열 부터 n열까지 검사 실시
				if (isPossible(row + 1)) // 이게 가능하면 dfs를 다시 recursive
					dfs(row + 1);
				else
					col[row + 1] = 0; // 만약 가능하지 않다면 더이상 dfs를 진행하지 않는다 => 백트래킹!
			}
			col[row] = 0; // 종료 전에 0으로 다시 초기화 해준다.
		}
	}

	private static boolean isPossible(int row) {
		// col[1]의 의미는 1행 *열이다.
		// col[1] = 1 => 1행 1열, col[2] = 3 => 2행 3열
		for (int i = 1; i < row; i++) {
			// 행이 같을때 열이 같은건 이미 앞전에 걸러짐 왜냐면 col[m]에 들어가는 애들은 1 2,3 4.. 이렇게 나눠서 들어가기 때문에 당연히
			// 열은 중복이 당연히 될수가 없다. 행의 구분만 있으면 완료.col안의 값이 행이니까 같은걸 골라내면됨
			if (col[i] == col[row]) 
				return false;
			if (Math.abs(col[i] - col[row]) == Math.abs(i - row)) // 대각선에 위치하는 x의 값과 y의 값이 같으면 대각선에 위치하는 거라 불가능
				return false;
		}
		return true;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		reader = new BufferedReader(new InputStreamReader(System.in));
		writer = new BufferedWriter(new OutputStreamWriter(System.out));

		n = Integer.parseInt(reader.readLine());

		col = new int[15]; // 15전 까지 (0은 안쓴다.)

		/* 1. */
		for (int i = 1; i <= n; i++) { // i는 열이다. 먼저 첫번째 열을 주루룩 검사한다. 처음은 1부터 검사한다.
			col[1] = i; // 이렇게되면 1열 i행 이런뜻이다..
			dfs(1);
		}

		writer.write(count + "");

		reader.close();
		writer.flush();
		writer.close();
	}

}

 

여기서 조금 중요하게 봐야하는 것은 col 배열이다. 이 문제를 풀다가 잘 풀리지 않는 사람들은 아마 대부분 2차원 배열을 사용했을 것이다. 나도 이 문제를 처음 접했을 때, 이걸 2차원 배열로 해야하나 하는 생각을 가졌었다. 하지만 코드를 살펴보면 알겠지만 같은 열을 기준으로 행의 경우와 대각선의 기준을 판별하기 때문에 어차피 열은 중복이 일어나지 않는다. 그렇기 때문에 2차원 배열을 사용하지 않고도 1차원 배열로도 충분히 해결할 수 있다. 여기서 col[row]의 값은 행으로 판단하고 안의 인덱스 row를 열로 판단하는 것이 중요하다. 이것이 이해가 안된다면 이것부터 이해하고 넘어가는 걸 추천한다. 

 

앞서 이야기 했지만 일단 이문제는 열 부분은 중복 될 수가 없다. 왜냐하면 열의 '각각' 의 인덱스에서 반복문을 통해서 행의 값들을 판별하고 있기 때문이다. dfs를 호출하는 기준도 row의 인덱스 '하나'이다! row를 여러개를 넣고 dfs를 호출하지 않는다는 점이 포인트이다. 즉 dfs를 통해서 늘어가는 것은 다음 행의 열검사.. 다음 행의 열 검사..이다.

 

먼저 n=4로 가정하자. 첫번째 열에서 1~4행을 검사하는 것은 /* 1. */에 있다. 여기서 col[1]을 정해줘버렸기 때문에 row는 기본 1부터 검사하는 것이다. main안에서라 그렇다.. 그리고 col안에 들어가는 것이 '행'이다! 즉 1열 1행부터 1열 4행까지 검사하는 것이다. 그리고 dfs를 호출하는데, 여기서 들어가는 값이 row이다 row는 1이다 근데 호출되는 dfs를 보면 검사부분은 모두 row+1을 하고 있다. 이것은 다음 열을 검사한다는 것이다. 즉 2열의 1~4행을 검사하는 것이다. 여기서 중요한 것이 나온다!!!!! isPossible() 함수를 보자. 해당하는 행과 대각선에 같은 값이 있는지(열은 자동적으로 겹칠 수 없다. 이게 이해가 안되면 코드를 자세히 읽어보자) 판별하고 있다! 왜 판별하느냐! 바로 백트래킹을 위해서이다. 여기서 행과 대각선이 겹치지 않는다면 더 가지를 깊게 들어가서 유망한 가지를 판별하면 된다! 근데 그게 아니라면? 문제의 조건과 부합하지 않기 때문에 더이상 들어가지 않고 가지를 쳐내면 된다. 이것이 백트래킹 부분이다. 

 

그렇게 열이 4열(n열)까지 진행되면 끝이다. 무사히 도달했고 백트래킹 조건 판별에 걸러지지 않았다는 것은 조건에 부합한다는 뜻이다. 그럼 count++을 해서 카운팅해주면 된다. 

 

 

 

어떤 문제든 처음 접하게 되면 어려울 수 있지만, 내가 설명을 해줄 수 있는 수준으로 이해를 한다면 반쯤은 성공이라고 본다. 공부는 남을 가르칠 수 있게 공부하자.