[알고리즘 공부] 백트래킹(Backtracking) 알고리즘

0. 개요

백준의 실버~골드 사이의 문제들을 보다보면 백트래킹 문제가 종종있는 것을 알 수 있다.

이전에는 그게 머임? 걍 대가리 박아보고 시작해야지 식으로 접근했는데

이제는 코테 공부 능지가 올라간 나이기에 정확히 개념부터 다시 깊게 공부해보려고 한다.

(근데 사실 그렇게 깊진 않음 ㅎ)

1. 알고리즘 개념

백트래킹이란 해를 찾는 도중 해가 아닐 경우, 되돌아가며 다시 해를 찾는 기법을 말한다.

대표적인 문제로 N-Queen 문제가 있다.

(N-Queen 문제는 N X N 칸으로 되어 있는 체스판에 퀸 N개를 서로가 서로에게 위협이 되지 않도록 배치하는 문제이다.)

 

백트래킹과 종종 함께 언급되는 알고리즘이 바로 DFS(깊이 우선 탐색)이다.

하지만 DFS와 가장 큰 차이점은 바로 가지치기라고 할 수 있다.

DFS는 모든 경우의 수를 탐색하는 반면, 백트래킹은 해당 경로가 해가 아닐 경우, 더이상 탐색하지 않고 되돌아간다.

즉, 특정 조건을 만족하는 경우만 탐색한다고 볼 수 있다.

 

2. 알고리즘 구조

1) 상태 표현

재귀 호출 시에 매개변수로 표현되는 부분해의 상태를 의미한다

N-Queen 문제에서는 지금까지 각각의 퀸이 어디에 위치되어 있는지에 대한 bool 값 배열일 수 있다.

(각 퀸은 서로 배치되어 있는 열과 행, 대각선이 겹쳐서는 안된다.)

2) 종료 조건

말 그대로 재귀가 멈춰야 되는 조건이다.

N-Queen 문제에서는 N개의 퀸이 모두 배치된 상태로 할 수 있다.

3) 후보 생성

현재 상태에서 다음에 어떤 선택을 할 수 있는지에 대해 후보를 생성하는 것이다.

N-Queen 문제에서는 현재 상태에서 배치가 가능한 퀸의 위치라고 볼 수 있다.

4) 제약 및 유망성 검사

선택한 후보가 어떠한 제약을 충족할 가능성이 있는지 판단하는 함수이다.

N-Queen 문제에서는 해당 퀸이 위치한 자리의 열과 행 혹은 대각선에 다른 퀸이 없는지 살펴 볼 수 있다.

5) 복귀(복원)

재귀 후 상태를 이전으로 돌리는 복귀 작업이다.

N-Queen 문제에서는 각 열, 행, 대각선에 대한 bool 값을 false로 초기화 하는 것으로 해결할 수 있다.

6) 가지치기

유망성 검사 후 더 이상 갈 필요가 없는 후보를 제거하는 것이다.

N-Queen 문제에서는 유망성 검사에서 false가 나온 후보들에 대해 재귀를 돌리지 않는 것으로 해결할 수 있다.

 

3. 알고리즘 구현

백트래킹은 Union-Find 나 세그먼트 트리처럼 어떤 형태를 갖고 있는게 아니기에 N-Queen 문제에 대한 해를 예시로 보여주겠다.

 

#include <stdio.h>
#include <vector>

using namespace std;

int N;
int result = 0;

/// <summary>
/// NQueen 해결
/// </summary>
/// 1) 상태 표현
/// <param name="c">특정 열에 퀸이 있는지</param>
/// <param name="dp">좌상->우하 방향 대각선에 퀸이 있는지(r+c)</param>
/// <param name="dm">우상->좌하 방향 대각선에 퀸이 있는지(r-c+n-1)</param>
/// <param name="n">퀸을 배치할 행</param>
void NQueen(vector<bool>& c, vector<bool>& dp, vector<bool>& dm, int n)
{
	// 2) 종료 조건
	if (n == N) // 모든 퀸 배치가 끝났다면
	{
		++result;
		return;
	}

	for (int i = 0; i < N; ++i)
	{
		// 4) 유망성 검사
		if (c[i] == false && dp[n + i] == false && dm[n - i + N - 1] == false)
		{
			// 3) 후보 생성
			c[i] = true;
			dp[n + i] = true;
			dm[n - i + N - 1] = true;

			NQueen(c, dp, dm, n + 1);

			// 4) 복귀
			c[i] = false;
			dp[n + i] = false;
			dm[n - i + N - 1] = false;
		}
	}

	// 5) 일종의 가지치기 (조건에 맞지 않으면 더이상 진행하지 않음
}

int main()
{
	scanf_s("%d", &N);

	auto c = vector<bool>(N, false);
	auto dp = vector<bool>(2 * N - 1, false);
	auto dm = vector<bool>(2 * N - 1, false);
	NQueen(c, dp, dm, 0);
	
	printf("%d", result);

	return 0;
}

 

4. 후기 

사실 NQueen 문제는 내가 대학교 1학년 때 코테나 어떤 알고리즘에 대한 개념이 없이 그냥 도전했다가 깨진 문제였다.

이번에 백트래킹을 확실하게 배우고, 실제로 활용하면서 이전에는 못 풀었지만 이제는 멋지게 풀어낸 나 자신이 너무 뿌듯했다!!