# Edit Step Ladders/조현태

## EditStepLadders/조현태¶

### 감상 및 설명 ¶

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

### 소스 ¶

```~cpp
#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;

}
```
last modified 2021-02-07 05:23:10
Processing time 0.0210 sec