C++ - DNA 조합 (2217) 백트래킹, 문자열

https://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1478&sca=3030 

JUNGOL

 

1. check(붙여질 문자열, 붙일 문자열) -> 문자열이 붙어지면 붙여서 반환, 붙어지지 않으면 ""(빈 문자열)반환

2. rec(현재 DNA 상태, 깊이, 앞서 붙인 문자열) 

#pragma warning(disable:4996)
#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
int n, ans = 0x7fffffff;
string dna[10], temp;
int freq[10], swi;

string check(string s1, string s2)
{
	int idx = 0;
	int s1Len = (int)s1.size();
	int s2Len = (int)s2.size();

	// 짧은 것을 기준으로 합니다.
	int Length = s1Len < s2Len ? s1Len : s2Len;

	for (int i = 0; i < Length; i++)
	{
		// 붙여질 문자의 끝부분과 붙일 문자의 첫 부분이 맞으면 인덱스 저장
		if (s1.substr(s1Len - 1 - i, i + 1) == s2.substr(0, i + 1))
		{
			idx = s1Len - 1 - i;
			swi = 1;
		}
	}
	if (swi == 1)
		return s1.substr(0, idx) + s2;
	else
		return "";
}

void rec(string dnaStr, int depth, string rear)
{
	// 구해놓은 답보다 길이가 길다면 되돌아갑니다.
	if (ans <= (int)dnaStr.size()) return;

	if (depth >= n)
	{
		ans = (int)dnaStr.size();
		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (freq[i]) continue;
		freq[i] = 1;

		// DNA 문자열이 비어있다면 현재 붙일 문자열을 그냥 인수로 사용합니다.
		if (dnaStr.empty() == 1)
			rec(dna[i], depth + 1, dna[i]);
		else
		{
			swi = 0;
			// 마지막으로 붙인 단어와 붙일 단어를 조합합니다.
			temp = check(rear, dna[i]);
			


			// 겹치는 부분이 없으면 그대로 붙여서 호출합니다.
			if (temp == "")
				rec(dnaStr + dna[i], depth + 1, dna[i]);

			// 겹치는 부분이 있다면 DNA 문자열에 구해놓은 문자열을 붙입니다. (중복 제거를 위해 )
			else
				rec(check(dnaStr, temp), depth + 1, dna[i]);

		}
		freq[i] = 0;
	}
}


int main()
{

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> dna[i];

	rec("", 0, "");

	cout << ans;
	return 0;
}