프로그래머스 - 단어 변환 (C++)

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

프로그래머스

 이번 문제는 주어진 단어의 알파벳 하나만을 변경하면서 주어진 target을 만들 수 있는지, 만들 수 있다면 최소 몇 번 알파벳을 바꿔야 하는지를 구하는 문제이다. 이번 문제는 BFS를 이용하여 풀 수 있는 문제이다. BFS 문제는 미로 탈출 등과 같이 2차원 배열을 이용하여 푸는 경우가 많았는데, 이 문제는 그렇지 않고 주어진 단어만 검사하면 되기 때문에 다른 BFS 문제에 비하면 쉬운 편이라 생각했다. 이 문제를 풀기 위해 구상한 절차는 다음과 같다.

1. 큐를 생성한 후, 시작 단어를 push 한다. 그리고 반복문을 이용해 탐색을 시작한다.
2. 만약 현재 큐의 front에 있는 단어가 target과 같다면, 현재까지 탐색한 횟수(시간)을 return한다.
3. 주어진 words를 모두 검사한다.
   1. 만약, i번째 단어가 이미 탐색한 단어라면 continue를 이용해 해당 단어를 건너뛴다.
   2. 현재 단어에서 i번째 단어로 바꿀 수 있는지 검사한다. 검사는 각 단어의 알파벳을 하나 하나 비교하여, 만약 다른 알파벳의 개수가 1개 이하라면 바꿀 수 있고 그렇지 않다면 바꿀 수 없다고 판단한다.
      
      1. 만약 바꿀 수 있다면 그 단어를 체크했음을 기록한 후, 큐에 그 단어를 push한다. 그리고 2번으로 돌아간다.

 

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

bool CanChange(string wordA, string wordB)
{
	int differentAlpNum = 0;

	for (int i = 0; i < wordA.size(); ++i)
	{
		if (wordA[i] != wordB[i])
		{
			++differentAlpNum;

			if (differentAlpNum > 1)
				return false;
		}
	}

	return true;
}

int solution(string begin, string target, vector<string> words)
{
	map<string, bool> checked;

	queue<pair<string, int>> q;
	q.push({ begin, 0 });
	checked[begin] = true;	

	while(!q.empty())
	{
		string curWord = q.front().first;
		int curTime = q.front().second;
		q.pop();

		if (curWord == target)
			return curTime;

		for (int i = 0; i < words.size(); ++i)
		{
			string nxtWord = words[i];

			if (checked[nxtWord] == true)
				continue;

			if (CanChange(curWord, nxtWord))
			{
				checked[nxtWord] = true;
				q.push({ nxtWord, curTime + 1 });
			}
		}
	}

	return 0;
}