백트래킹
백트래킹은 DFS에서 발전한 탐색 전략입니다.
모든 경우의 수를 탐색해야 하는 문제라면, 일반적으로 BFS보다 DFS와 백트래킹을 사용하는 것이 메모리를 줄일 수 있습니다. (BFS는 Queue의 메모리를 소비하기 때문입니다.)
백트래킹은 DFS로 탐색하다, 정답이 아니라면 더 이상 해당 경로를 탐색하지 않고 다음 경로를 탐색하는 방법입니다.
백트래킹으로 문제를 풀 때, 가장 중요한 점은 해당 문제를 트리 구조로 만들 수 있는지 여부입니다.
아래 예제에서는 이에 대해 설명하겠습니다.
가지치기
백트래킹에서, 정답이 아닌 경로를 잘라내는 방법을 가지치기라고 합니다.
가지치기를 잘하면, 효율이 증가합니다. (전반적인 로직의 효율은 전처리와 완전히 동일합니다.)
백트래킹의 활용
백트래킹의 가장 대표적인 문제로 N-Queen 문제가 있습니다.
아래 그림은 4*4의 체스판에서 4개의 Queen이 존재할 수 있는 경우를 찾는 과정입니다.
그림과 같이 트리 구조가 완성되는 문제라면, 기본적인 백트래킹을 사용할 수 있는 문제입니다.
1.
첫 번째 줄에 퀸을 놓을 수 있는 경우를 검색합니다. (깊이가 1)
2.
두 번째 줄에 퀸을 놓을 수 있는 경우를 검색합니다. (깊이가 2)
3.
이와 같은 방식으로 다음 줄에 퀸을 놓을 수 있는 경우를 검색합니다. 놓을 수 없으면 다음 두 가지를 실행합니다.
•
3.1 현재 놓여있는 퀸을 제거합니다.
•
3.2 다음 줄을 검색하지 않고 종료합니다.
4.
마지막으로 퀸 네 개를 모두 놓았다면, N-Queen 문제를 성공하고 Count를 증가시킵니다.
N-Queen문제 코드
백준 9663번 N-Queen 문제의 코드입니다.
var sr = new StreamReader(Console.OpenStandardInput());
var sw = new StreamWriter(Console.OpenStandardOutput());
var N = int.Parse(sr.ReadLine());
var cols = new int[N + 1];
var totalCount = NQueen(1);
sw.WriteLine(totalCount);
int NQueen(int row)
{
var total = 0;
if (row == N + 1)
{
return 1;
}
else
{
for (int c = 1; c <= N; c++)
{
cols[row] = c;
if (isPossible(row))
{
total += NQueen(row + 1);
}
}
}
return total;
}
bool isPossible(int bound)
{
for (var r = 1; r < bound; r++)
{
if (cols[bound] == cols[r])
return false;
if (Math.Abs(cols[bound] - cols[r]) == Math.Abs(bound - r))
return false;
}
return true;
}
sw.Flush();
sw.Close();
sr.Close();
C#
복사
