[종만북] 6장. 완전 탐색 (1) 원소 고르기, BOGGLE

1. 예제: n개의 원소 중 m개를 고르는 모든 경우의 수 찾기

#include <bits/stdc++.h>
using namespace std;

void printPicked(vector<int>& picked) {
	for (int p : picked) {
		cout << p << ", ";
	}
	cout << "\n";
}

// [0, n) 구간의 숫자들 중 toPick 개를 뽑는 모든 경우의 수를 출력하는 함수
void pick(int n, vector<int>& picked, int toPick) {
	if (toPick == 0) {printPicked(picked); return; } // 뽑을게 더 없으면 picked 출력 후 종료
	int smallest = picked.empty() ? 0 : picked.back() + 1; // 고를 수 있는 가장 작은 숫자 계산 (초기값 0)
	for (int next = smallest; next < n; ++next) {
		picked.push_back(next);
		pick(n, picked, toPick - 1);
		picked.pop_back();
	}
}

int main() {
	vector<int> vec;
	pick(5, vec, 3); // 5개의 원소 중 3개 뽑는 모든 경우의 수
}

재귀 호출을 통해 완전 탐색을 쉽게 구현할 수 있다. 이를 이용하여 특정 조건을 만족하는 조합을 모두 생성할 수도 있다. 

 

2. 예제: BOGGLE (난이도 하)

#include <bits/stdc++.h>
using namespace std;

vector<vector<char>> wordmap;

// 상대 좌표 목록
const int dx[8] = { -1,-1,-1,1,1,1,0,0 };
const int dy[8] = { -1,0,1,-1,0,1,-1,1 };

bool inRange(int y, int x) {
	if (y < 0 || y > 4) return false;
	if (x < 0 || x > 4) return false;
	return true;
}

bool hasWord(int y, int x, string word) {
	// Base Cases
	if (!inRange(y, x)) return false; // 범위 밖
	if (wordmap[y][x] != word[0]) return false; // 첫 글자가 일치하지 않음
	if (word.size() == 1) return true; // 한 글자가 일치

	// 인접한 8칸 검사 (다음 좌표, 단어는 맨 앞에거 하나 떼고 보내기
	for (int i = 0; i < 8; i++) {
		if (hasWord(y + dy[i], x + dx[i], word.substr(1))) return true;
	}

	// 반복을 돌아도 없으면 종료
	return false;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		wordmap.resize(5);
		for (int i = 0; i < 5; i++) {
			wordmap[i].resize(5);
			for (int j = 0; j < 5; j++)
				cin >> wordmap[i][j];
		}

		int n;
		cin >> n;
		while (n--) {
			string str; cin >> str;
			bool isFind = false;

			for (int i = 0; i < 5; i++) {
				for (int j = 0; j < 5; j++) {
					if (hasWord(i, j, str)) {
						cout << str << " YES" << endl;
						isFind = true;
					}
					if (isFind) break;
				}
				if (isFind) break;
			}
			if (!isFind) cout << str << " NO" << endl;
		}
	}

}

문제 바로가기: https://www.algospot.com/judge/problem/read/BOGGLE 

이 문제는 완전 탐색으로는 시간 복잡도가 너무 커서 통과되지 않는다. 하지만 이 풀이에도 배울 것이 많이 있었다.

• Base Case에서 범위를 처리해주자. 난 원래 범위 검사를 배열에 직접 접근할 때 많이 했었는데 base case에 넣어두니 더 깔끔해졌다.
• 상대 좌표는 dx, dy 배열을 만들어서 반복문 한번으로 탐색하게 한다. 몇번 사용한 적이 있었던 기법이다.
• substr(1) 을 통해서 문자열의 일부만 매개변수로 넘길 수 있다.

 

3. 완전 탐색 레시피

1. 걸리는 시간은 정답의 개수에 비례한다. 따라서 최대 크기의 입력을 가정했을 때 답의 개수가 제한 시간 안에 생성할 수 있는지 확인하자.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 쪼개자. 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.
3. 그 중 하나의 조각을 선택해 답의 일부를 만들고 나머지 답은 재귀 호출을 통해 완성한다.
4. Base Case는 조각이 하나 이하로 남은 경우로 처리한다.