EditStepLadders/조현태

== EditStepLadders/조현태 ==
  === 감상 및 설명 ===
  아아 이 귀차니즘이란..ㅎㅎ..
  소스 중간에 귀차니즘의 압박으로 중복된 부분이 있지만.. 귀찮으니까 수정하진 않도록 하였음.^^
  map을 이용한 캐시가 되어있다.
  아까의 벽돌 문제와 알고리즘이 유사해서 그대로 배껴쓰는 센스를 보였음. ^^V

 === 소스 ===
#include <iostream>
#include <vector>
#include <map>

using namespace std;

const char DEBUG_READ[] = "cat\ndig\ndog\nfig\nfin\nfine\nfog\nlog\nwine\n";
const int MAX_WORD_NUMBER = 25000;

#define TRUE 1
#define FALSE 0

void AddWord(char* readData, vector<const char*>& myWords)
{
	while(0 != *readData && NULL != readData)
	{
		myWords.push_back(readData);
		readData = strchr(readData, '\n');
		*readData = 0;
		++readData;
	}
}

bool IsEditStepLadder(int smallOne, int bigOne, vector<const char*>& myWords)
{
	static map<int, bool> mapOfLadder;
	if (mapOfLadder.end() != mapOfLadder.find(smallOne * MAX_WORD_NUMBER + bigOne))
	{
		return mapOfLadder[smallOne * MAX_WORD_NUMBER + bigOne];
	}

	bool myResult = FALSE;
	int smallLength = strlen(myWords[smallOne]);
	int bigLength = strlen(myWords[bigOne]);
	if (smallLength == bigLength)
	{
		int differenceWordCount = 0;
		for (register int i = 0; i < bigLength; ++i)
		{
			if (myWords[smallOne][i] != myWords[bigOne][i])
				++differenceWordCount;
		}
		if (1 == differenceWordCount)
			myResult = TRUE;
	}
	else if (1 == bigLength - smallLength)
	{
		int differenceWordCount = 0;
		int gab = 0;
		for (register int i = 0; i < bigLength; ++i)
		{
			if (myWords[smallOne][i + gab] != myWords[bigOne][i])
			{
				++differenceWordCount;
				if (1 == differenceWordCount)
					++gab;
			}
		}
		if (1 == differenceWordCount)
			myResult = TRUE;
	}
	else if (-1 == bigLength - smallLength)
	{
		int differenceWordCount = 0;
		int gab = 0;
		for (register int i = 0; i < smallLength; ++i)
		{
			if (myWords[smallOne][i] != myWords[bigOne][i + gab])
			{
				++differenceWordCount;
				if (1 == differenceWordCount)
					++gab;
			}
		}
		if (1 == differenceWordCount)
			myResult = TRUE;
	}
	mapOfLadder[smallOne * MAX_WORD_NUMBER + bigOne] = myResult;
	return myResult;
}

void SuchNextWord(vector<const char*>& myWords, int wordNumber, vector<int>& myWordStack, vector<int>& bestWordStack)
{
	vector<int> suchWordList;
	suchWordList.reserve(myWords.size());
	//// 다음에 나올 단어를 찾아낸다. ////
	if (0 == myWordStack.size())
	{
		for (register unsigned int i = wordNumber + 1; i < myWords.size(); ++i)
			suchWordList.push_back(i);
	}
	else
	{
		for (register unsigned int i = wordNumber + 1; i < myWords.size(); ++i)
		{
			if (IsEditStepLadder(wordNumber, i, myWords))
			{
				suchWordList.push_back(i);
			}
		}
	}
	//// 다음 단어가 없을때. ////
	if (0 == suchWordList.size())
	{
		if (myWordStack.size() > bestWordStack.size())
		{
			bestWordStack = myWordStack;
		}
		return;
	}

	//// 다음 단어를 선택해 봅니다. ////
	for (register int i = 0; i < (int)suchWordList.size(); ++i)
	{
		myWordStack.push_back(suchWordList[i]);
		SuchNextWord(myWords, suchWordList[i], myWordStack, bestWordStack);
		myWordStack.pop_back();
	}
}

void main()
{
	int boxNumber = 0;
	const char* readData = DEBUG_READ;
	char* myStrings = new char[strlen(readData) + 1];
	strcpy(myStrings, readData);
	

	vector<const char*> myWords;
	AddWord(myStrings, myWords);

	vector<int> myWordStack;
	vector<int> bestWordStack;
	SuchNextWord(myWords, 0, myWordStack, bestWordStack);

	cout << bestWordStack.size() << endl;
	delete myStrings;

}

---

EditStepLadders