프로그래머스 단어 변환

문제 : https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환 | 프로그래머스

#include <string>
#include <vector>
#include <queue>
using namespace std;

void DeleteGraph(int iSize, int** Graph)
{
	for (int i = 0; iSize; ++i)
	{
		delete[] Graph[i];
	}
	delete[] Graph;
}
bool isAdjacency(const string& words1, const string& words2)
{
	int iLength = words1.size();

	int stack = 0;
	for (int i = 0; i < iLength; ++i)
	{
		if (words1[i] != words2[i])
		{
			++stack;
			if (stack > 1)
				return false;
		}
	}
	return true;
}

int BFS(int iStart, int** Graph, const vector<string>& words, const string& target)
{
	int iSize = words.size();

	bool* visit = new bool[iSize];

	for (int i = 0; i < iSize; ++i)
	{
		for (int j = 0; j < iSize; ++j)
		{
			if (i == iStart)
				visit[i] = true;
			else
				visit[i] = false;
		}
	}

	// BFS
	queue<int> queBFS;
	queBFS.push(iStart);

	int iPath = 2;

	int iLayer = 1;
	while (!queBFS.empty())
	{
		for (int i = 0; i < iLayer; ++i)
		{
			int index = queBFS.front();
			queBFS.pop();

			for (int i = 0; i < iSize; ++i)
			{
				if (Graph[index][i] == 1 && words[i] == target)
					return iPath;

				if (Graph[index][i] == 1 && visit[i] == false)
				{
					queBFS.push(i);
					visit[i] = true;
				}
			}
		}
		iLayer = queBFS.size();
		// 한 레이어가 끝날 때마다 카운트 해줘야함.
		++iPath;
	}

	delete[] visit;

	return 60;
}

int solution(string begin, string target, vector<string> words) {

	int iSize = words.size();
	int iLength = begin.size();

	int** Graph = new int* [iSize];
	for (int i = 0; i < iSize; ++i)
	{
		Graph[i] = new int[iSize];
	}

	//그래프 제작
	for (int i = 0; i < iSize; ++i)
	{
		for (int j = i; j < iSize; ++j)
		{
			if (i == j)
			{
				Graph[i][j] = 0;
				continue;
			}

			if (isAdjacency(words[i], words[j]))
			{
				Graph[i][j] = 1;
				Graph[j][i] = 1;
			}
			else
			{
				Graph[i][j] = 0;
				Graph[j][i] = 0;
			}
		}
	}

	vector<int> vecStart;
	// 시작할 수 있는 인덱스 들의 후보
	for (int i = 0; i < iSize; ++i)
	{
		if (isAdjacency(begin, words[i]))
		{
			if (words[i] == target)
			{
				DeleteGraph(iSize, Graph);
				return 1;
			}
			vecStart.push_back(i);
		}
	}

	// begin과 인접한 인덱스가 없다
	if (vecStart.size() == 0)
	{
		DeleteGraph(iSize, Graph);
		return 0;
	}

	int iMinPathLength = 60;
	int iStartSize = vecStart.size();
	for (int i = 0; i < iStartSize; ++i)
	{
		int iPath = BFS(vecStart[i], Graph, words, target);

		if (iPath < iMinPathLength)
			iMinPathLength = iPath;
	}

	DeleteGraph(iSize, Graph);
	// delete Graph
	if (iMinPathLength == 60)
		return 0;

	return iMinPathLength;
}