dfs_teaching_1062

백준 dfs의 1062번 문제 가르침을 풀이해보도록 하겠습니다.

문제 URL : https://www.acmicpc.net/problem/1062

dfs로 풀어보는 중 입니다.. 제가 순환이나 재귀적으로 로직을 잘 못짜서 시간이 좀 걸릴 것 같아요

아래는 수정중인 코드라 엉망입니다.ㅎㅎ

오픈된 테스트케이스에서 요구하는 답은 나왔는데 시간이 늦어서 지금 딱 기분 좋을때 자려고합니다 ㅎㅎ. 입력형식 맞추고 백준에서 정답으로 제출하면 왠지 틀렸다고 할 것 같아서요 ㅎ ㅎ

Source Code :

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int alphavet[26] = { 0, };


int dfs(vector<string> input_data, vector<char> candidateList, int visit[26], int i, int k) {
	int cnt = 0;

	if ((k < 0) || (i >= candidateList.size())) {
		return 0;
	}
	
	/*for (int j = i + 1; j < 26; j++) {
		if (alphavet[j]) {
			for (int i = 0; i < input_data.size(); i++) {
				for (int j = 0; j < input_data[i].size(); j++) {
					if (!(visit[input_data[i][j] - 97])) {
						return 0;
					}
				}
				cnt++;
			}
			return cnt + dfs(input_data, j, k - 1);
		}
	}*/
	
	// copy
	/*vector<char> nextCandidateList;
	for (int j = i + 1; j < candidateList.size(); j++) {
		nextCandidateList.push_back(candidateList[j]);
	}*/

	// copy
	int tmp_visit[26] = { 0, };
	for (int j = 0; j < 26; j++) {
		tmp_visit[j] = visit[j];
	}

	// i번째 알파벳을 배운 후 읽을 수 있는 문장 세기
	tmp_visit[candidateList[i]-97] = 1;
	for (int p = 0; p < input_data.size(); p++) {
		int boool = 1;

		for (int q = 0; q < input_data[p].size(); q++) {
			if (!(tmp_visit[input_data[p][q] - 97])) {	// 하나라도 읽지 못하면 break
				boool = 0;
				break;
			}
		}
		if (boool) {
			cnt++;
		}
	}

	int max_cnt = dfs(input_data, candidateList, tmp_visit, i + 1, k-1);

	for (int j = i + 2; j < candidateList.size(); j++) {
		int tmp_cnt = dfs(input_data, candidateList, tmp_visit, j, k-1);
		if (max_cnt < tmp_cnt) {
			max_cnt = tmp_cnt;
		}
	}
	if (cnt < max_cnt) {
		return max_cnt;
	}
	return cnt;

	/*
	for (int j = i + 1; j < candidateList.size(); j++) {
		if (cnt + dfs(input_data, candidateList, tmp_visit, j, k) > cnt + dfs(input_data, candidateList, tmp_visit, j, k))
		return cnt + dfs(input_data, candidateList, tmp_visit, j, k);
	}*/
}

int main(void) {
	int n = 3, k=10;
	int cnt = 0;
	vector<string> input_data = { "antarctica","antahellotica","antacartica" };
	int visit[26] = { 0, };

	visit['a' - 97] = 1, visit['n' - 97] = 1, visit['t' - 97] = 1, visit['i' - 97] = 1, visit['c' - 97] = 1;
	k = k - 5;

	if (k < 1) {
		for (int i = 0; i < input_data.size(); i++) {
			if (input_data[i] == "antatica") {
				cnt++;
				break;
			}
		}
		cout << cnt << endl;
		return 0;
	}

	// 입력된 애들 표시해두기~
	for (int i = 0; i < input_data.size(); i++) {
		for (int j = 4; j < input_data[i].size() - 4; j++) {
			alphavet[input_data[i][j] - 97] = 1;
		}
	}
	
	vector<char> candidateList;

	for (int i = 0; i < 26; i++) {
		if (alphavet[i] && !(visit[i])) {
			candidateList.push_back(i + 97);
		}
	}
/*	candidateList.push_back('r');
	candidateList.push_back('h');
	candidateList.push_back('e');
	candidateList.push_back('l');
	candidateList.push_back('o');*/

	/*for (int i = 0; i < 26; i++) {
		//if (alphavet[i]) {//
		dfs(input_data, i, k);
		//}
	}*/

	int max_cnt = dfs(input_data, candidateList, visit, 0, k);

	for (int i = 1; i < candidateList.size(); i++) {
		int tmp_cnt = dfs(input_data, candidateList, visit, i, k);
		if (max_cnt < tmp_cnt) {
			max_cnt = tmp_cnt;
		}
	}

	cout << max_cnt << endl;
	
	cin >> n;
	return 0;
}

(수정중)

개인이 공부하고 포스팅하는 블로그입니다. 작성한 글 중 오류나 틀린 부분이 있을 경우 과감한 지적 환영합니다!