백트래킹
백트래킹의 주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 깊이 우선 탐색을 사용한다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아간다. 시도해보지 않은 다른 해결 방법이 있으면 시도한다. 해결 방법이 더 없으면 더 이전의 분기점으로 돌아간다. 모든 트리의 노드를 검사해도 답을 못 찾을 경우, 이 문제의 해결책은 없는 것이다.
보통 재귀 함수로 구현된다. 재귀로 파생된 해결 방법은 하나 이상의 변수가 필요한데 , 이것은 현재 시점에서 적용할 수 있는 변수값들을 알고 있다. 퇴각검색은 깊이 우선 탐색과 대략 같으나 기억 공간은 덜 차지한다. 현재의 상태를 보관하고 바꾸는 동안만 차지한다.
탐색 속도를 높이기 위해, 재귀 호출을 하기 전에 시도할 값을 정하고 조건(전진 탐색의 경우)을 벗어난 값을 지우는 알고리즘을 적용할 수 있다. 아니면 그 값을 제외한 다른 값들을 탐색할 수도 있다.
(위키출처)
한마디로, 문제를 해결해나가다가 이게 답이 될 수 없다고 판단하면 되돌아가는 방식이다.
그 방향으로 나아가지 않고 되돌아가는 것을 가지치기라고 한다.
이 가지치기를 하게 될 조건을 잘 생각해야하는 것이 포인트이다.
보통 모든 경우의 수를 탐색해야할 경우에 유용하게 쓰인다.
상태를 트리로써 나타낼 수 있을 때 유용하게 쓰인다.
방식에 따라 DFS 말고도 BFS를 사용하는 백트래킹이 있다.
근데 보통 모든 경우의 수를 따져봐야할 경우 DFS가 낫다.
BFS로 구현하면 큐의 크기가 매우 커질 수 있어 주의해야하기 때문.
그리고 구현 용이성도 DFS가 더 좋다.
근데 트리의 깊이가 무한대일 경우 DFS가 시작과 동시에 무한 루프에 빠져서 나갈 수가 없다.
DFS를 활용한 백트래킹의 예시를 살펴보자
예제
N-Queen이라는 매우 유명한 백준 백트래킹 문제이다.
백준 N-Queen
풀이 아이디어
퀸이 공격할 수 있는 경우라면 탐색을 더 이상 할 필요가 없다.
근데 퀸이 공격할 수 있는 경우는 다음과 같다
- 같은 행에 있을 때
- 같은 열에 있을 때
- 대각선 상에 있을 때
그렇다면 같은 행에 있는 경우는 아예 없으므로, 한 행에는 하나의 퀸만 있을 수 있다.
그렇다면 퀸의 좌표를 하나의 벡터로 나타낼 수 있다.
벡터의 인덱스가 행이고 값이 열인 것이다.
예를 들어 vec[1]가 2일때, 퀸은 (1,2)에 있는 것이다.
그렇다면 임의의 i, j에 있는 퀸이 같은 열에 있는 경우는 다음과 같다
vec[i] == vec[j]
또한 대각선에 있는 경우는 다음과 같다
vec[i]와 vec[j]의 차 == i와 j의 차
그러면, N을 받았을 때, 0~N-1까지의 값들을 하나의 vec에 중복없이 모든 경우의 수를 구하되, 위의 조건에 맞는다면 탐색을 중지하고 되돌아가면 된다.
코드
#include <iostream>
using namespace std;
int answer = 0;
int vec[15];
bool checkCanAttack(int depth)
{
if (depth < 1) return false;
for (int i = 0; i < depth; i++)
{
if ((abs(i - (depth)) == abs(vec[i] - vec[depth])) || vec[i] == vec[depth])
{
return true;
}
}
return false;
}
void backTracking(int n, int depth)
{
if (depth == n)
{
answer++;
return;
}
for (int i = 0; i < n; i++)
{
vec[depth] = i;
if (!checkCanAttack(depth))
{
backTracking(n, depth + 1);
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
backTracking(n, 0);
cout << answer;
}회고
이 문제에서 시간 초과로 상당히 애를 먹었는데 그 이유가 바로 벡터를 쓴 것이었다.
벡터에 너무 익숙해진 나머지 그냥 처음에 아래처럼 벡터로 풀면서 push_back, pop_back을 사용하며 풀이를 해버렸다.
완전 동일한 로직인데도 불구하고 시간초과로 통과가 되지 않아 혹시나 싶어 배열로 바꿔보니 통과가 됐다..
가능하다면 알고리즘 문제에서는 배열을 사용하는 습관을 들여야할 것 같다.
//시간초과 났던 코드...
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int answer = 0;
bool checkCanAttack(vector<int> vec)
{
int curIdx = vec.size()-1;
if (curIdx < 1) return false;
for (int i = 0; i < curIdx; i++)
{
if ((abs(i - (curIdx)) == abs(vec[i] - vec[curIdx])) || vec[i] == vec[curIdx])
{
return true;
}
}
return false;
}
void backTracking(int n, vector<int> vec)
{
//공격 가능 시 되돌아감
if (checkCanAttack(vec))
{
return;
}
if (vec.size() == n)
{
answer++;
return;
}
for (int i = 0; i < n; i++)
{
vec.push_back(i);
backTracking(n, vec);
vec.pop_back();
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> vec;
backTracking(n, vec);
cout << answer;
}