From Dusk Till Dawn/조현태

소스코드 ¶

~cpp
#include <iostream>
#include <vector>
#include <string>

using namespace std;

const char DEBUG_READ[] = "2\n3\nUlm Muenchen 17 2\nUlm Muenchen 19 12\nUlm Muenchen 5 2\nUlm Muenchen\n10\nLugoj Sibiu 12 6\nLugoj Sibiu 18 6\nLugoj Sibiu 24 5\nLugoj Medias 22 8\nLugoj Medias 18 8\nLugoj Reghin 17 4\nSibiu Reghin 19 9\nSibiu Medias 20 3\nReghin Medias 20 4\nReghin Bacau 24 6\nLugoj Bacau";

const int BUFFER_SIZE = 255;

#define TRUE 1
#define FALSE 0

struct STown
{
	STown(const char* inputName)
	{
		name = inputName;
	}
	string name;
	vector<STown*> nextTown;
	vector<int> startTime;
	vector<int> timeDelay;
};

vector<STown*> g_myTowns;
string g_suchStartTown;
string g_suchEndTown;
int g_minimumDelayTime = 0;

STown* SuchOrAddTown(const char* townName)
{
	for (register unsigned int i = 0; i < g_myTowns.size(); ++i)
	{
		if (g_myTowns[i]->name == townName)
			return g_myTowns[i];
	}
	g_myTowns.push_back(new STown(townName));
	return g_myTowns[g_myTowns.size() - 1];
}

const char* Parser(const char* readData)
{
	char startStationName[BUFFER_SIZE];
	char endStationName[BUFFER_SIZE];
	int startTime;
	int delayTime;
	int sizeOfTimeTable;

	sscanf(readData, "%d", &sizeOfTimeTable);
	readData = strchr(readData, '\n') + 1;
	for(register int i = 0; i < sizeOfTimeTable; ++i)
	{
		sscanf(readData, "%s %s %d %d", startStationName, endStationName, &startTime, &delayTime);

		STown* thisStation = SuchOrAddTown(startStationName);
		thisStation->nextTown.push_back(SuchOrAddTown(endStationName));
		thisStation->startTime.push_back(startTime % 24);
		thisStation->timeDelay.push_back(delayTime);
		
		readData = strchr(readData, '\n') + 1;
	}
	sscanf(readData, "%s %s", startStationName, endStationName);
	g_suchStartTown = startStationName;
	g_suchEndTown = endStationName;
	readData = strchr(readData, '\n');

	if (NULL != readData)
		return readData + 1;
	else
		return NULL;
}

bool isDeadTime(int inputTime)
{
	if (18 > inputTime % 24 && 6 < inputTime % 24)
		return TRUE;
	return FALSE;
}

void SuchTown(STown* startTown, STown* endTown)
{
	//// 시작 준비 ////
	vector< vector<STown*> > allSuchList;
	vector<int> allDelay;
	vector<STown*> newTown;
	int newAddPoint;
	newTown.push_back(startTown);
	allDelay.push_back(0);
	allSuchList.push_back(newTown);

	do{
		//// 가장 시간이 낮은 경우에 대해서 연산을 수행합니다. ////
		newAddPoint = allSuchList[0].size() - 1;
		STown* suchTown = allSuchList[0][allSuchList[0].size() - 1];
		for (register int i = 0; i < (int)(suchTown->nextTown.size()); ++i)
		{
			if (suchTown->timeDelay[i] <= 12 && !(isDeadTime(suchTown->startTime[i]) || isDeadTime(suchTown->startTime[i] + suchTown->timeDelay[i])))
			{
				vector<STown*> suchTownList = allSuchList[0];
				suchTownList.push_back(suchTown->nextTown[i]);
				allSuchList.push_back(suchTownList);
				
				if (allDelay[0] % 24 <= suchTown->startTime[i])
					allDelay.push_back(allDelay[0] + suchTown->startTime[i] - (allDelay[0] % 24) + suchTown->timeDelay[i]);
				else
					allDelay.push_back(allDelay[0] + (suchTown->startTime[i] + 24) - (allDelay[0] % 24) + suchTown->timeDelay[i]);

				if (g_suchEndTown == suchTown->nextTown[i]->name)
				{
					if ((0 != g_minimumDelayTime && g_minimumDelayTime > allDelay[allDelay.size() - 1]) || 0 == g_minimumDelayTime)
						g_minimumDelayTime = allDelay[allDelay.size() - 1];
				}
			}
		}
		allSuchList.erase(allSuchList.begin());
		allDelay.erase(allDelay.begin());
		//// 동일한 위치로 간것과 전체 시간을 초과한 것을 삭제합니다. ////
		for (register int i = newAddPoint; i < (int)allSuchList.size(); ++i)
		{
			if (0 != g_minimumDelayTime && g_minimumDelayTime < allDelay[i])
			{
				allSuchList.erase(allSuchList.begin() + i);
				allDelay.erase(allDelay.begin() + i);
			}
			else
			{
				bool isSame = FALSE;
				for (register int j = 0; j < (int)allSuchList[i].size(); ++j)
				{
					for (register int k = j + 1; k < (int)allSuchList[i].size(); ++k)
					{
						if (allSuchList[i][j] == allSuchList[i][k])
						{
							allSuchList.erase(allSuchList.begin() + i);
							allDelay.erase(allDelay.begin() + i);
							--i;
							isSame = TRUE;
							break;
						}
					}
					if (isSame)
						break;
				}

			}
		}

		if (0 == allSuchList.size())
			break;
		//// 가장 시간이 낮은 경우를 제일 앞으로 둡니다. ////
		int minimumDelayPoint = 0;
		int minimumDelay = allDelay[0];
		for (register int i = 1; i < (int)allSuchList.size(); ++i)
		{
			if (minimumDelay > allDelay[i])
			{
				minimumDelay = allDelay[i];
				minimumDelayPoint = i;
			}
		}
		allDelay[minimumDelayPoint] = allDelay[0];
		vector<STown*> bufferSTown = allSuchList[minimumDelayPoint];
		allDelay[0] = minimumDelay;
		allSuchList[0] = bufferSTown;
	}while(0 != allSuchList.size());
}

void freeMemory()
{
	for (register int i = 0; i < (int)g_myTowns.size(); ++i)
		delete g_myTowns[i];
}

void main()
{
	int numberOfTestCase = 0;
	const char* readData = DEBUG_READ;
	sscanf(readData, "%d", &numberOfTestCase);
	readData = strchr(readData, '\n') + 1;
	for (register int i = 0; i < numberOfTestCase; ++i)
	{
		//// 초기화 ////
		g_myTowns.clear();
		g_suchStartTown.clear();
		g_suchEndTown.clear();
		g_minimumDelayTime = 0;

		//// 연산 ////
		readData = Parser(readData);
		SuchTown(SuchOrAddTown(g_suchStartTown.c_str()), SuchOrAddTown(g_suchEndTown.c_str()));
		freeMemory();
		if (0 == g_minimumDelayTime)
			cout << "There is no route Vladimir can take." << endl;
		else
			cout << "Vladimir needs " << g_minimumDelayTime / 24 << " litre(s) of blood. " << endl;
	}
}