[G4] 백준 1062번 가르침 C++ 백트래킹

리뷰

 

에잉.. 코드 한줄 차이로 너무 헤맨 문제였다.

https://www.acmicpc.net/problem/1062

 

전역 변수

• n, k, ans : 단어의 개수 n, 배울 수 있는 글자의 수 k, 정답을 저장할 변수 ans
• v : 방문 처리용 배열
• path : 중복 제거용 벡터
• lst : 입력된 단어를 저장할 문자열 배열, 입력 문자의 최대 크기인 50으로 초기화 한다.

 

함수

1. bt

void bt(int level)

 

백트래킹을 통해 배울 수 있는 단어 개수의 최대값을 구하는 함수

1. 매개변수로 level을 받아 각 재귀 단계 즉 배운 글자의 개수를 명시해 준다.
2. 기저조건은 level이 k - 5가 되었을때이다. cnt를 0으로 초기화 하고 n개의 문자열을 순회한다.
3. flag를 1로 설정하고 각 문자열이 방문처리 되어있는지 확인해 준다.
4. 단, 이때 첫번째 4개 단어와 마지막 4개 단어는 이미 배웠다고 가정하고 탐색해 주어야 한다.
5. 만약 단어의 모든 글자가 배운 글자일 경우 cnt를 증가시켜준다.
6. 모든 단어의 탐색이 완료 되었을 경우 ans와 비교하여 더 큰값을 ans로 만들어 준 뒤 리턴해준다.
7. 기저조건에 도달하지 못했을 경우 a ~ z를 순회하며 아직 방문하지 않은 글자를 찾아 방문처리를 진행해 준다.
8. 이때 path를 사용해 주는 이유는 중복을 제거해 주기 위함이다.
9. 재귀가 끝난 경우 path에서 배웠던 글자를 빼주고, 방문처리도 다시 원상복구 시켜준다.

 

문제풀이

1. n, k값을 입력 받고, lst배열에 n개의 문자열을 집어넣어준다.
2. a, n, t, i, c이 다섯글자는 무조건 들어오므로 이미 배웠다고 가정해 줄 것이다.
3. 방문배열에 각각의 알파벳의 아스키코드에 해당하는 인덱스를 방문처리를 진행해 준다.
4. 만약 k가 5보다 작을 경우 정답은 무조건 0이므로 백트래킹을 진행하지 않아도 된다.
5. 만약 k가 5보다 크거나 같을 경우 재귀 레벨을 0부터 시작하여 백트래킹 함수를 호출한다.
6. 모든 탐색이 종료된 후 ans변수에 저장된 값을 출력해 준다.

 

참고 사항

"antic" 다섯 글자를 이미 배웠다고 가정하므로 k가 4이하일때는 백트래킹을 실행하면 안된다.

1 4
antatica

 

해당 예제의 출력값이 1이 되면 안된다.

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;

int n, k, ans;
int v[125];
vector<int> path;
string lst[50];

void bt(int level) {
	if (level >= k - 5) {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			int flag = 1;
			int len = lst[i].size();
			for (int j = 4; j < len - 4; j++) {
				if (!v[lst[i][j]]) {
					flag = 0;
					break;
				}
			}
			if (flag) cnt++;
		}
		ans = max(ans, cnt);
		return;
	}

	for (int i = 'a'; i <= 'z'; i++) {
		if (v[i]) continue;
		if (!path.empty() && path.back() < i) continue;
		v[i] = 1;
		path.push_back(i);
		bt(level + 1);
		path.pop_back();
		v[i] = 0;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;

	for (int i = 0; i < n; i++) cin >> lst[i];
	string s = "antic";
	for (int i = 0; i < 5; i++) v[s[i]] = 1;
	if (k >= 5) bt(0);
	cout << ans;
}