백준 알고리즘 중급 - 브루트 포스 : 재귀 (연습) - 2

지금까지 강의 중에 제일 어려웠다.

백트래킹 부분이 많이 약한 것 같다. 보통 앞의 문제를 풀어보면 요령이 생겨

뒤의 문제를 곧잘 푸는데 이건 정말 손도 못 댔던 것 같다.

그만큼 더 잘 이해하고 넘어가야 하는 이유다..

하나하나 곱씹으면서 정리해보자.

-

* N -Queen (high) : 크기가 n*n인 체스판 위에 n개의 queen을 놓는 경우의 수를 구하는 문제다.

9663번: N-Queen

- queen은 상하, 좌우, 대각선까지 다 갈 수 있다. 따라서 queen의 위치를 잡았을 때, 상하좌우대각선에 다른 퀸이 없는 지 확인해줘야 한다.

- row를 하나씩 늘려감과 동시에, 방문한 col과 대각선의 위치를 기록하면서 재귀를 해준다. 위치 기록은 일차원 배열에 넣고도 가능하다. 그림으로 보면 이해가 쉽다.

같은 col 기록

같은 오른쪽 대각선 기록

같은 왼쪽 대각선 기록

- 위에서부터 a[row][col]일 때, col, row+col, row-col+n 과 같은 인덱스로 방문 여부를 기록할 수 있다.

#include <iostream>
bool c[15][15], check_col[15], check_dig[40], check_dig2[40];

using namespace std;

int n;

bool check(int row, int col) {
	if (check_col[col])
		return false;

	if (check_dig[row + col])
		return false;

	if (check_dig2[row - col + n])
		return false;

	return true;
}

int calc(int row) {
	if (row == n) {
		return 1;
	}
	int cnt = 0;
	for (int col = 0; col < n; col++) {
		if (check(row, col)) {
			check_col[col] = true;
			check_dig[row + col] = true;
			check_dig2[row - col + n] = true;
			c[row][col] = true;
			cnt += calc(row + 1);
			check_col[col] = false;
			check_dig[row + col] = false;
			check_dig2[row - col + n] = false;
			c[row][col] = true;
		}
	}

	return cnt;
}

int main()
{
	cin >> n;
	cout << calc(0) << '\n';
	return 0;
}

 

* 스도쿠 (high) : 주어진 수에서 스도쿠를 완성하면 되는 문제다.

2580번: 스도쿠

- 같은 행, 같은 열, 그리고 같은 3*3 공간 안에 1~9가 중복 없이 하나씩 존재해야 한다.

- c[i][j]에 i행 안의 j의 존재를, c2[i][j]에 i열 안의 j의 존재를, c3[i][j]에 i번째 3*3 공간 안의 j의 존재 여부를 기록한다. 

- a[i][j]의 3*3 공간 순서는 (i/3) * 3 + (j/3) 와 같이 구하면 된다.

 - 9*9 공간에 있는 81개의 수를 재귀를 이용하여 일일이 방문해 수를 넣고 조건을 따져본다.

#include <iostream>
using namespace std;
int a[10][10];
bool c[10][10];
bool c2[10][10];
bool c3[10][10];

int square(int x, int y) {
	return (x / 3) * 3 + (y / 3);
}

bool go(int k) {
	if (k == 81) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << a[i][j] << ' ';
			}
			cout << '\n';
		}
		return true;
	}
	int x = k / 9; int y = k % 9;
	if (a[x][y] != 0) {
		return go(k + 1);
	} else {
		for (int i = 1; i <= 9; i++) {
			if (c[x][i] == 0 && c2[y][i] == 0 && c3[square(x, y)][i] == 0) {
				c[x][i] = c2[y][i] = c3[square(x, y)][i] = true;
				a[x][y] = i;
				if (go(k + 1)) {
					return true;
				}
				a[x][y] = 0;
				c[x][i] = c2[y][i] = c3[square(x, y)][i] = false;
			}
		}
	}
	return false;
}

int main()
{
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> a[i][j];
			if (a[i][j] != 0) {
				c[i][a[i][j]] = true;
				c2[j][a[i][j]] = true;
				c3[square(i, j)][a[i][j]] = true;
			}
		}
	}

	go(0);

	return 0;
}

- c[x][i], c2[y][i], c3[square(x,y)][i] 에 true를 넣고, a[x][y]에 i를 넣어준 뒤에 go(k+1) 로 가는데, 여기서 왜 true를 리턴하는지 잘 이해가 안 된다. 혹시나 해서 true를 빼고 하니까 틀렸다고 나온다. 강의에서도 따로 언급을 안 하는데.. 왜 true를 리턴해야 값이 올바르게 나오는지 다시 보고 이해되면 왜 그런지 남겨 놓자.

 

* 스도미노쿠 (high) : 스토쿠에 조건이 좀 추가된 버전이다.

4574번: 스도미노쿠

- 스도쿠와 같은 조건을 만족하면서 인접한 서로 다른 두 수가 1,2 1,3 1,4 ... 8,7 8,9 이런 식으로 나와줘야 한다. 이를 도미노라고 한다.

- 스도쿠 문제와 유사하긴 하지만, 생각해줘야 할 게 많아서 좀 어려웠다..

#include <iostream>
#include <cstring>
#include <tuple>
using namespace std;
int a[10][10];
bool c[10][10];
bool c2[10][10];
bool c3[10][10];
bool domino[10][10];
int n = 9;
int dx[] = { 0, 1 };
int dy[] = { 1, 0 };
pair<int, int> convert(string s) {
	return make_pair(s[0] - 'A', s[1] - '1');
}
int square(int x, int y) {
	return (x / 3) * 3 + (y / 3);
}
bool can(int x, int y, int num) {
	return c[x][num] == false && c2[y][num] == false && c3[square(x, y)][num] == false;
}
void check(int x, int y, int num, bool what) {
	c[x][num] = what;
	c2[y][num] = what;
	c3[square(x, y)][num] = what;
}
bool check_range(int x, int y) {
	return 0 <= x && x < n && 0 <= y && y < n;
}
bool go(int z) {
	if (z == 81) {
		for (int i = 0; i<n; i++) {
			for (int j = 0; j<n; j++) {
				cout << a[i][j];
			}
			cout << '\n';
		}
		return true;
	}
	int x = z / n;
	int y = z%n;
	if (a[x][y] != 0) {
		return go(z + 1);
	}
	else {
		for (int k = 0; k<2; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (!check_range(nx, ny)) {
				continue;
			}
			if (a[nx][ny] != 0) continue;
			for (int i = 1; i <= 9; i++) {
				for (int j = 1; j <= 9; j++) {
					if (i == j) continue;
					if (domino[i][j]) continue;
					if (can(x, y, i) && can(nx, ny, j)) {
						check(x, y, i, true);
						check(nx, ny, j, true);
						domino[i][j] = domino[j][i] = true;
						a[x][y] = i;
						a[nx][ny] = j;
						if (go(z + 1)) {
							return true;
						}
						check(x, y, i, false);
						check(nx, ny, j, false);
						domino[i][j] = domino[j][i] = false;
						a[x][y] = 0;
						a[nx][ny] = 0;
					}
				}
			}
		}
	}
	return false;
}
int main() {
	int tc = 1;
	while (true) {
		memset(c, false, sizeof(c));
		memset(c2, false, sizeof(c2));
		memset(c3, false, sizeof(c3));
		memset(domino, false, sizeof(domino));
		memset(a, 0, sizeof(a));
		int m;
		cin >> m;
		if (m == 0) break;
		for (int i = 0; i<m; i++) {
			int n1, n2;
			string s1, s2;
			cin >> n1 >> s1 >> n2 >> s2;
			int x1, y1, x2, y2;
			tie(x1, y1) = convert(s1);
			tie(x2, y2) = convert(s2);
			a[x1][y1] = n1;
			a[x2][y2] = n2;
			domino[n1][n2] = domino[n2][n1] = true;
			check(x1, y1, n1, true);
			check(x2, y2, n2, true);
		}
		for (int i = 1; i <= 9; i++) {
			string s;
			cin >> s;
			int x, y;
			tie(x, y) = convert(s);
			a[x][y] = i;
			check(x, y, i, true);
		}
		cout << "Puzzle " << tc << '\n';
		go(0);
		tc += 1;
	}
	return 0;
}

- 일단 문자+숫자 형식으로 입력 받은 수를 숫자+숫자 형식으로 변환해주고 위치에 들어갈 수를 기록한다.

- 인접한 두 수의 정보와 스도쿠 문제를 풀 때 기록해줬던 3가지 정보도 업데이트 해준다.

- 마찬가지로 1~9의 위치 정보와 3가지 정보도 업데이트 해준다.

- 인접한 두 위치를 구한 뒤에, 스도쿠의 조건과 도미노 조건을 만족하는 두 수를 넣어주면서 재귀를 해준다.

- 상당히 까다로웠다..

 

* 알파벳 (high) : 중복하지 않고 지날 수 있는 최대 길이를 찾는 문제다.

1987번: 알파벳

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int go(vector<string> &board, vector<bool> &check, int x, int y) {
	int ans = 0;
	for (int k = 0; k<4; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size()) {
			if (check[board[nx][ny] - 'A'] == false) {
				check[board[nx][ny] - 'A'] = true;
				int next = go(board, check, nx, ny);
				if (ans < next) {
					ans = next;
				}
				check[board[nx][ny] - 'A'] = false;
			}
		}
	}
	return ans + 1;
}
int main() {
	int n, m;
	cin >> n >> m;
	vector<string> board(n);
	for (int i = 0; i<n; i++) {
		cin >> board[i];
	}
	vector<bool> check(26);
	check[board[0][0] - 'A'] = true;
	cout << go(board, check, 0, 0) << '\n';
	return 0;
}

- 아직까지 재귀를 짜는 요령이 부족한 것 같다. 그나마 이 챕터에서는 제일 할만한 문제였는데, 요령이 잘 안 떠올랐다. 

- 브루트 포스 재귀는 방문 여부를 기록했다가 다시 원상복구 하는 식으로 반복문을 돌리는데 그 포인트가 어딘지 잘 찾아서 식을 세워야 할 것 같다.

- 

솔직히 좀 현타가 왔다.

아무 것도 제대로 풀어내지 못 했기 때문이다.

나중에 다시 한번 복습을 하면서 내껄로 만드는 과정이 필요한 챕터다.

꼭 복습하고 넘어가자!

정리 끝.