백트래킹(backtracking)
백트래킹 기법은 해를 탐색하는 기법 중 하나로, 한정 조건을 가진 문제에서 가능한 모든 경우의 수를 탐색한다. 결정 문제나 최적화 문제를 해결할 수 있는 방법이기도 하다. 우리말로는 퇴각 검색이라고도 한다.
vs 깊이 우선 탐색(DFS)
일반적으로 백트래킹의 구현은 BFS나 DFS를 통해 구현한다. 하지만 백트래킹의 핵심 아이디어는 불필요한 경우를 차단하는 데 있다. 해를 탐색하는 과정 중 해당 과정이 해의 조건을 벗어날 경우, 이전의 상태로 돌아가 다른 선택을 시도한다. 한 경로를 끝까지 탐색하는 DFS와는 이러한 차별점이 있다.
응용
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int l, c;
char car[20];
bool check[20];
void makepw(int s, int size, int vow, int conso) {
if (size == l) {
if ((vow) && (conso >= 2)) {
for (int i = 0; i < c; i++) {
if (check[i]) {
cout << car[i];
}
}
cout << "\n";
}
}
else {
for (int i = s; i < c; i++) {
if (check[i] == false) {
check[i] = true;
if ((car[i] == 'a') || (car[i] == 'e') || (car[i] == 'i') || (car[i] == 'o') || (car[i] == 'u')) {
vow++;
makepw(i + 1, size + 1, vow, conso);
vow--;
}
else {
conso++;
makepw(i + 1, size + 1, vow, conso);
conso--;
}
check[i] = false;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> l >> c;
for (int i = 0; i < c; i++) {
cin >> car[i];
check[i] = false;
}
sort(car, car + c);
makepw(0, 0, 0, 0);
return 0;
}특정 조건을 만족하는 해를 탐색하는, 백트래킹의 기법을 구현한 것이다. 길이가 지정한 길이만큼이며, 모음(vow)이 적어도 1개 이상, 자음(conso)이 적어도 2개 이상 존재할 경우, 해를 반환하는 것이다.
#include <iostream>
using namespace std;
int r, c, m = 0;
char board[25][25];
bool abc[30] = { false, };
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
void dfs(int y, int x, int cnt) {
abc[(int)(board[y][x] - 'A')] = true;
m = max(m, cnt);
for (int i = 0; i < 4; i++) {
if ((y + dy[i] >= 0) && (y + dy[i] < r) && (x + dx[i] >= 0) && (x + dx[i] < c)) {
if (abc[(int)(board[y + dy[i]][x + dx[i]] - 'A')] == false) {
dfs(y + dy[i], x + dx[i], cnt + 1);
abc[(int)(board[y + dy[i]][x + dx[i]] - 'A')] = false;
}
}
}
}
int main() {
cin >> r >> c;
for (int i = 0; i < r; i++) {
cin >> board[i];
}
dfs(0, 0, 1);
cout << m;
return 0;
}DFS를 통해 백트래킹을 실시한다.
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 2e9;
int m, ans = MAX;
vector<pair<int, int>> home;
vector<pair<int, int>> chicken;
bool chi[15];
void chickendistance(int s, int size) {
int a, dis;
if (size == m) {
a = 0;
for (int i = 0; i < home.size(); i++) {
dis = MAX;
for (int j = 0; j < chicken.size(); j++) {
if (chi[j] == true) {
dis = min(dis, (abs(home.at(i).first - chicken.at(j).first) + abs(home.at(i).second - chicken.at(j).second)));
}
}
a += dis;
}
ans = min(a, ans);
}
else {
for (int i = s; i < chicken.size(); i++) {
if (chi[i] == false) {
chi[i] = true;
chickendistance(i + 1, size + 1);
chi[i] = false;
}
}
}
}
int main() {
int n, k = 0;
int city[55][55];
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> city[i][j];
if (city[i][j] == 1) {
home.push_back({ i,j });
}
else if (city[i][j] == 2) {
chicken.push_back({ i,j });
chi[k] = false;
k++;
}
}
}
chickendistance(0, 0);
cout << ans;
return 0;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int sudoku[9][9];
int anscnt;
vector<pair<int, int>> blank;
bool anscheck(int y, int x) {
int r, c;
for (int i = 0; i < 9; i++) {
if (sudoku[y][x] == sudoku[y][i]) {
if (i == x) {
continue;
}
else {
return false;
}
}
}
for (int i = 0; i < 9; i++) {
if (sudoku[y][x] == sudoku[i][x]) {
if (i == y) {
continue;
}
else {
return false;
}
}
}
r = (y / 3) * 3;
c = (x / 3) * 3;
for (int i = r; i < (r + 3); i++) {
for (int j = c; j < (c + 3); j++) {
if (sudoku[i][j] == 0) {
continue;
}
else {
if (sudoku[y][x] == sudoku[i][j]) {
if ((i == y) && (j == x)) {
continue;
}
else {
return false;
}
}
}
}
}
return true;
}
void putans(int cnt) {
if (cnt == anscnt) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cout << sudoku[i][j] << " ";
}
cout << "\n";
}
exit(0);
}
else {
for (int i = 1; i <= 9; i++) {
sudoku[blank.at(cnt).first][blank.at(cnt).second] = i;
if (anscheck(blank.at(cnt).first, blank.at(cnt).second)) {
putans(cnt + 1);
}
sudoku[blank.at(cnt).first][blank.at(cnt).second] = 0;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> sudoku[i][j];
if (sudoku[i][j] == 0) {
blank.push_back({ i,j });
}
}
}
anscnt = blank.size();
putans(0);
return 0;
}스도쿠 판을 입력받으면 공백, 즉 채워야 하는 칸을 문제 배열에 삽입하고 문제 배열을 모두 채울 수 있도록 백트래킹을 실시한다. 이때, 해를 만족할 조건은 스도쿠의 조건 그대로 세로열, 가로열, 자신이 포함된 3×3 영역 안에 중복되는 수가 없어야 할 것을 조건으로 한다.
#include <bits/stdc++.h>
using namespace std;
int n, ans = 0;
int board[16];
void queen(int y) {
if (y == n) {
ans++;
return;
}
else {
bool q;
for (int i = 0; i < n; i++) {
q = true;
for (int j = 0; j < y; j++) {
if ((board[j] == i) || (abs(y - j) == abs(board[j] - i))) {
q = false;
break;
}
}
if (q) {
board[y] = i;
queen(y + 1);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
queen(0);
cout << ans;
return 0;
}조건을 생각하는 것이 너무 어려워 결국 검색을 통해 다른 풀이의 도움을 받아 해결했다. 보드 크기(n)만큼 탐색을 실시하여 완료되면 그 해를 반환하는 방식이다. 테스트 케이스를 실행했을 때, 시간이 너무 오래걸려 TLE가 나올 줄 알았는데, 이게 정답이었다.
#include <bits/stdc++.h>
using namespace std;
int n, ans = 0;
vector<vector<int>> move_up(vector<vector<int>> prev) {
int cnt;
vector<vector<int>> v;
v = prev;
for (int j = 0; j < n; j++) {
cnt = 0;
for (int i = 0; i < n; i++) {
if (v.at(i).at(j) == 0) {
cnt++;
}
else {
swap(v.at(i - cnt).at(j), v.at(i).at(j));
i -= cnt;
cnt = 0;
}
}
}
for (int i = 0; i < (n - 1); i++) {
for (int j = 0; j < n; j++) {
if ((v.at(i).at(j) != 0) && (v.at(i + 1).at(j) == v.at(i).at(j))) {
v.at(i).at(j)++;
v.at(i + 1).at(j) = 0;
}
}
}
for (int j = 0; j < n; j++) {
cnt = 0;
for (int i = 0; i < n; i++) {
if (v.at(i).at(j) == 0) {
cnt++;
}
else {
swap(v.at(i - cnt).at(j), v.at(i).at(j));
i -= cnt;
cnt = 0;
}
}
}
return v;
}
vector<vector<int>> move_down(vector<vector<int>> prev) {
int cnt;
vector<vector<int>> v;
v = prev;
for (int j = 0; j < n; j++) {
cnt = 0;
for (int i = (n - 1); i >= 0; i--) {
if (v.at(i).at(j) == 0) {
cnt++;
}
else {
swap(v.at(i + cnt).at(j), v.at(i).at(j));
i += cnt;
cnt = 0;
}
}
}
for (int i = (n - 1); i > 0; i--) {
for (int j = 0; j < n; j++) {
if ((v.at(i).at(j) != 0) && (v.at(i - 1).at(j) == v.at(i).at(j))) {
v.at(i).at(j)++;
v.at(i - 1).at(j) = 0;
}
}
}
for (int j = 0; j < n; j++) {
cnt = 0;
for (int i = (n - 1); i >= 0; i--) {
if (v.at(i).at(j) == 0) {
cnt++;
}
else {
swap(v.at(i + cnt).at(j), v.at(i).at(j));
i += cnt;
cnt = 0;
}
}
}
return v;
}
vector<vector<int>> move_left(vector<vector<int>> prev) {
int cnt;
vector<vector<int>> v;
v = prev;
for (int i = 0; i < n; i++) {
cnt = 0;
for (int j = 0; j < n; j++) {
if (v.at(i).at(j) == 0) {
cnt++;
}
else {
swap(v.at(i).at(j - cnt), v.at(i).at(j));
j -= cnt;
cnt = 0;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < (n - 1); j++) {
if ((v.at(i).at(j) != 0) && (v.at(i).at(j + 1) == v.at(i).at(j))) {
v.at(i).at(j)++;
v.at(i).at(j + 1) = 0;
}
}
}
for (int i = 0; i < n; i++) {
cnt = 0;
for (int j = 0; j < n; j++) {
if (v.at(i).at(j) == 0) {
cnt++;
}
else {
swap(v.at(i).at(j - cnt), v.at(i).at(j));
j -= cnt;
cnt = 0;
}
}
}
return v;
}
vector<vector<int>> move_right(vector<vector<int>> prev) {
int cnt;
vector<vector<int>> v;
v = prev;
for (int i = 0; i < n; i++) {
cnt = 0;
for (int j = (n - 1); j >= 0; j--) {
if (v.at(i).at(j) == 0) {
cnt++;
}
else {
swap(v.at(i).at(j + cnt), v.at(i).at(j));
j += cnt;
cnt = 0;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = (n - 1); j > 0; j--) {
if ((v.at(i).at(j) != 0) && (v.at(i).at(j - 1) == v.at(i).at(j))) {
v.at(i).at(j)++;
v.at(i).at(j - 1) = 0;
}
}
}
for (int i = 0; i < n; i++) {
cnt = 0;
for (int j = (n - 1); j >= 0; j--) {
if (v.at(i).at(j) == 0) {
cnt++;
}
else {
swap(v.at(i).at(j + cnt), v.at(i).at(j));
j += cnt;
cnt = 0;
}
}
}
return v;
}
void backtr(vector<vector<int>> v, int k) {
if (k < 5) {
backtr(move_up(v), k + 1);
backtr(move_down(v), k + 1);
backtr(move_left(v), k + 1);
backtr(move_right(v), k + 1);
}
else if (k == 5) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ans = max(ans, v.at(i).at(j));
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tmp;
vector<vector<int>> board;
cin >> n;
for (int i = 0; i < n; i++) {
vector<int> v;
for (int j = 0; j < n; j++) {
v.push_back(0);
cin >> tmp;
while (tmp > 1) {
tmp /= 2;
v.at(j)++;
}
}
board.push_back(v);
}
backtr(board, 0);
cout << (1 << ans);
return 0;
}2048 게임에 대한 이해가 어느 정도 필요했다. 사실 백트래킹 기법보다 DFS에 더 가까운 방식이다. 보드를 이동하면 모든 숫자들을 이동방향으로 움직이고, 합칠 수 있는지(같은 숫자가 이동방향으로 맞닿아 있는지) 확인하여 합친 다음, 한 번 더 이동시킨다.
References
ChanBLOG) 알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제
팔만코딩경) 백트래킹(BackTracking)
안녕하세요