브루트포스[3]:백트레킹(backtracking)

알고리즘 중 하나인 백트레킹 설명과 문제풀이.

 

백트레킹(backtracking, 퇴각검샘)

백트레킹은 유망성 검사를 만족하는 경우 모든 조합의 수를 살펴보는 것이다. 유망성 검사를 만족하지 않은 경우 많은 부분 조합들을 배제할 수 있고 모든 경우의 수를 모두 찾는 것보다 훨씬 빠르고 풀이 시간이 단축된다.

 

구현방법은 DFS와 같은 구조이지만 유망성 점검을 하냐 안하냐로 구분된다. 어떤 노드의 유망성 점검후, 유망하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. 

 

브루트포스는 모든 방법을 만드는 것이나, 백트레킹은 아무리 해봤자 의미가 없다 싶을 때 호출을 중단하는 것.

 

 

backtraking에서 부분조합을 배제하는 과정

 

DFS는 말단 노드까지 방문 후 해를 만족하는지 검사

 

---

백트레킹 알고리즘의 설명에 관해서 매우 설명이 잘되있는 블로그가 있기 때문에 참고하면 좋을 것 같다!

idea-sketch.tistory.com/29

[알고리즘] 되추적(Backtracking)을 알아보자.

 

백트레킹 문제 풀이

9663 N-Queen : www.acmicpc.net/problem/9663

백트레킹 문제 중 가장 대표되는 문제

NxN크기의 체스판 위에 Queen을 N개 놓는 방법의 수를 구하는 문제

 퀸을 체스판에서 가로, 세로, 대각선 모두 겹치게 둘 수가 없다.

 

브루트 포스를 이용할 경우

1. 각각의 칸에 퀸이 있을 수도 있고 없을 수도 있음.

칸의 개수 :  N^2, 경우의 수 : 2^(N^2) = 2^(NxN)

고로 경우의 수가 너무 많다.

->

2. 각 행과 열마다 퀸이 있을 수 있는 위치는 하나

N^N 이 경우도 수가 너무 많다.

->

3. 행으로 봤을 때 1열에 퀸을 둘 경우

2행에서는 1열을 제외한 나머지 공간에 퀸을 놓개된다.

고로 N!으로 경우의 수를 줄일 수 있다.

 

 

 

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

int n;
int a[15][15];
bool check_row[30]; //i번 열에 퀸이 있으면 true, 없으면 false
bool check_column[30]; // i번 행에 퀸이 있으면 true
bool check_dig1[30]; // i번 대각선에 퀸이 있으면 true
bool check_dig2[30]; // ''
bool check(int y, int x) { // 가로 세로 대각선에 퀸이 이미 놓여져 있는지 체크
	if (check_row[y]) {
		return false;
	}
	if (check_column[x]) {
		return false;
	}
	if (check_dig1[y + x]) {
		return false;
	}
	if (check_dig2[n - x + y]) {
		return false;
	}
	return true;
}

int go(int h) {
	if (h == n) {
		return 1;
	}
	int ret = 0;
	
	for (int w = 0; w < n; ++w) {
		if (check(h, w)) {	// 유망성 검사
			a[h][w] = h;
			check_row[h] = true;
			check_column[w] = true;
			check_dig1[h + w] = true;
			check_dig2[n - w + h] = true;
			ret += go(h + 1);
			check_row[h] = false;
			check_column[w] = false;
			check_dig1[h + w] = false;
			check_dig2[n - w + h] = false;

		}
	}

	return ret;
}

int main(void) {
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; ++i) v[i] = -1;
	cout << go(0);
}

 

 

2580 스도쿠 : www.acmicpc.net/problem/2580

스도쿠 문제는 원래 백트레킹 알고리즘으로는 해결 할 수 없다.

하지만 이 문제는 입력이 백트래킹 알고리즘으로 풀 수 있는 입력만 주어졌으므로 해결가능하다. 

Y,X축과 사각형에 이미 수가 있는지 배열을 통하여 저장하고 각 구간마다 유망성 검사를 진행하여 풀이하였다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

#define squqre(y, x) (y/3)*3 + (x/3)
int a[10][10];
bool visitedY[10][10];	//Y축에 수가 있으면 true
bool visitedX[10][10];	//X축에 수가 있으면 true
bool visitedS[10][10];	//작은 사각형에 수가 있으면 true
vector<pair<int, int> > v;

bool check(int y, int x, int num) {
	if (visitedX[y][num]) return false;
	if (visitedY[x][num]) return false;
	if (visitedS[squqre(y, x)][num]) return false;
	return true;
}

int go() {
	int ret = 0;
	if (v.size() == 0) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) {
				printf("%d ", a[i][j]);
			}
			puts("");
		}
		return 1;
	}

	for (int i = 1; i < 10; ++i) {
		int ny = v.front().first;
		int nx = v.front().second;
		if (check(ny, nx,i)) {
			v.erase(v.begin());
			a[ny][nx] = i;
			visitedX[ny][i] = visitedY[nx][i] = visitedS[squqre(ny, nx)][i] = true; 
			ret = go();
			a[ny][nx] = 0;
			v.insert(v.begin(), make_pair(ny, nx));
			visitedX[ny][i] = visitedY[nx][i] = visitedS[squqre(ny, nx)][i] = false;
		}
		if (ret == 1) return 1;
	}
	return ret;
}

int main(void) {
	for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) {
		scanf("%d", &a[i][j]);
		if (a[i][j] == 0) {
			v.push_back(make_pair(i, j));
		}
		else {	//빈칸이 아니면 미리 준비를 해둠
			visitedX[i][a[i][j]] = true;
			visitedY[j][a[i][j]] = true;
			visitedS[squqre(i, j)][a[i][j]] = true;
		}
	}
	go();
}

 

4574 스도미노쿠 : www.acmicpc.net/problem/4574

스도쿠와 유사하지만 조건처리를 하나 더해야 하는 문제

어떤 도미노를 사용했는지 안했는지 기록하여 해결, ij도미노를 묶어서 두어야 한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

#define squqre(y, x) (y/3)*3 + (x/3)
int a[10][10];
bool domino[10][10];
bool visitedY[10][10];
bool visitedX[10][10];
bool visitedS[10][10];
int dy[2] = { 0, 1 };
int dx[2] = { 1, 0 };
bool check(int y, int x, int num) {
	if (visitedX[y][num]) return false;
	if (visitedY[x][num]) return false;
	if (visitedS[squqre(y, x)][num]) return false;
	return true;
}
int cnt = 0;
int visited[10000];
int go(int z) {
	if (z == 80 && visited[cnt]==0) {
		visited[cnt] = 1;
		printf("Puzzle %d\n", cnt);
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) printf("%d", a[i][j]);
			puts("");
		}
	return 1;
	}
	int y = z / 9, x = z % 9;
	if (a[y][x] != 0) {
		go(z + 1);
	}
	else {
		for (int i = 0; i < 2; ++i) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny<9 && nx < 9 && a[ny][nx] != 0) continue;
			for (int p = 1; p < 10; ++p) {
				for (int q = 1; q < 10; ++q) {
					if (domino[p][q]) continue;
					if (p == q) continue;
					int num1, num2;
					num1 = p, num2 = q;
					if (check(y, x, num1) && check(ny, nx, num2)) {
						a[y][x] = num1;
						a[ny][nx] = num2;
						domino[p][q] = true;
						domino[q][p] = true;
						visitedX[y][num1] = true;
						visitedY[x][num1] = true;
						visitedS[squqre(y, x)][num1] = true;
						visitedX[ny][num2] = true;
						visitedY[nx][num2] = true;
						visitedS[squqre(ny, nx)][num2] = true;
						
						if (go(z + 1)==1) {
							return 1;
						}
						a[y][x] = a[ny][nx] = 0;
						domino[p][q] = domino[q][p] = visitedX[y][num1] = visitedY[x][num1] = visitedS[squqre(y, x)][num1] = false;
						visitedX[ny][num2] = visitedY[nx][num2] = visitedS[squqre(ny, nx)][num2] = false;
					}

				}
			}
		}
	}
	return 0;
}
int main(void) {
	while (++cnt) {
		memset(a, 0, sizeof(a));
		memset(domino, 0, sizeof(domino));
		memset(visitedY, 0, sizeof(visitedY));
		memset(visitedX, 0, sizeof(visitedX));
		memset(visitedS, 0, sizeof(visitedS));
		int n, num1, num2;
		int y1, x1, y2, x2;
		char ch1, ch2, ch3, ch4;
		scanf("%d", &n);
		if (n == 0)break;

		for (int i = 0; i < n; ++i) {
			scanf("%d %c%c %d %c%c", &num1, &ch1, &ch2, &num2, &ch3, &ch4);
			y1 = ch1 - 'A';
			x1 = ch2 - '1';
			a[y1][x1] = num1;
			y2 = ch3 - 'A';
			x2 = ch4 - '1';
			a[y2][x2] = num2;
			domino[num1][num2] = true;
			domino[num2][num1] = true;
			visitedX[y1][num1] = true;
			visitedY[x1][num1] = true;
			visitedS[squqre(y1, x1)][num1] = true;
			visitedX[y2][num2] = true;
			visitedY[x2][num2] = true;
			visitedS[squqre(y2, x2)][num2] = true;

		}
		for (int i = 1; i < 10; ++i) {
			scanf(" %c%c", &ch1, &ch2);
			y1 = ch1 - 'A';
			x1 = ch2 - '1';
			a[y1][x1] = i;
			visitedX[y1][i] = true;
			visitedY[x1][i] = true;
			visitedS[squqre(y1, x1)][i] = true;
		}
		go(0);
		
	}

}

 

1987 알파벳 : www.acmicpc.net/problem/1987

같은 알파벳이 적힌 칸을 두 번 지날 수 없다는 조건을 지키면서 최대한 몇칸을 지날수 있는지 구하는 문제

visited : 어떤 알파벳을 방문 했는지

go (x, y : 현재위치, cnt : 방문한 칸의 수)

#include <iostream>
#include <vector>
using namespace std;

int ans;
int h, w;
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

char a[21][21];
bool visited[50];
int go(int y, int x, int cnt) {
	if (ans < cnt) ans = cnt;
	for (int i = 0; i < 4; ++i) {
		int ny = y + dy[i];
		int nx = x + dx[i];
        //범위 안에 있는지, 알파벳을 방문 한적 있는지?
		if (0 <= ny && ny < h && 0 <= nx && nx < w && visited[a[ny][nx]-'A'] == false) {
			visited[a[ny][nx]-'A'] = true; //방문표시
			go(ny, nx, cnt+1); //방문
			visited[a[ny][nx]-'A'] = false; //방문표시해제
		}
	}

	return 0;
}
int main(void) {
	cin >> h >> w;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			cin >> a[i][j];
		}
	}
	visited[a[0][0] - 'A'] = true;
	go(0, 0, 1);
	cout << ans;
}