From Dusk Till Dawn/조현태

No older revisions available

FromDuskTillDawn/조현태 ¶

감상 및 설명 ¶

불쌍한 뱀파이어..T.T
나이가 들어도 밤에 밖에 못다니다니.. 이동네는 아템빨도 없나??ㅎㅎ
일단 수많은 귀차니즘으로 약간의 전역변수를 사용하였으며..
문제에서 처럼 여러개의 테스트 케이스도 받도록 수정하였다.
참고 : 나름대로 약간의 최적화가 되어있다. 그러나~ vector가 아닌 list를 사용한다면 좀더 효과적일듯하다.ㅎ 이런 귀차니즘~
소스코드 ¶

~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;
	}
}
----
FromDuskTillDawn