[프로그래머스] 단어변환

문제

문제설명

hit에서 cog를 가는 방법의 갯를 리턴

 

시행착오

처음에 DFS로 풀려고 시도했는데 words를 탐색할때 앞으로 갔다가 뒤로 갔다가 하니깐 visit 처리가 꼬이면서 결국 gg

풀면서도 bfs로 풀면 쉽겠다 생각이 들어서 40분동안 dfs로 풀다가 결국 bfs로 넘어가서 쉽게 품...

하지만, bfs에서 계속 2,3번이 안나옴 알고보니 꼭 words가 세글자가 아닌 10글자까지 가능한 것... 문제 잘 읽자..

문제풀이

1) begin값에서 변환가능한 모든 경우의 수를 queue에 넣음 

2) bfs를 돌리며 target이 나오는 순간 모든 함수 종료

3) 트리구조를 떠올리며 자식 노드로 이동 할때 +1을 해주기 위해 queue를 페어로 구현하였고 두번째 값에 노드 번째를 나타냄.

 

난이도

★★★☆☆

dfs 하면서 오기 생겨서 테스트케이스 많이 생성하게 됨... dfs로 다시 구현 예정..

 

코드

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
bool visit[50] = { false, };
 
bool flag = false;
int bfs(string begin, vector<string> words, int num, string target)
{
	int answer = 100;
	queue<pair<string, int>> q;
	q.push({ begin,0 });
	int sizeQueue = 0; 
	int ansNum = 0;
	while(!q.empty())
	{ 
		if (flag == true)
			break; 
		string begin = q.front().first;
		int ansNum = q.front().second;
		q.pop();
		ansNum++;  
		for (int w = 0; w < words.size(); w++)
		{
			int cnt = 0;
			for (int i = 0; i < begin.length(); i++)
			{
				if (begin[i] == words[w][i])
				{
					cnt++;
				}
			} 
			if (cnt == begin.size()-1 && !visit[w])
			{
				if (words[w] == target)
				{
					flag = true; 
					answer = ansNum;
					break;
				}
				visit[w] = true;
				q.push({ words[w],ansNum });
			}
		} 
		sizeQueue = q.size(); 
	}

	return answer;


}

int solution(string begin, string target, vector<string> words)
{
	int answer = 100;
	int in = 100;
	 
	in = bfs(begin, words, 0, target);
	answer = min(in, answer);
	in = 0;
	 
	if (answer == 100)
		answer = 0;
	return answer;
}

int main()
{
	cout << solution("hit", "cog", { "hot", "dot", "dog", "lot", "log","cog" }) << endl;// hot -> dot -> dog -> log -> cog 
 	//cout << solution("hit", "hhh", { "hhh", "hht" }) << endl; //2
	//cout << solution("zzz", "zzz", { "zzz" }) << endl;
	//cout << solution("hit", "zzz", { "zzz" }) << endl;
	//cout << solution("hit", "zzz", { "zzz", "zyz", "xzz", "xyz", "hyt", "hyz", "xiz", "hiz" }) << endl;// 4 :  hyt -> xiz -> xzz -> zzz //4번



}