프로그래머스 단어변환

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

코딩테스트 연습 - 단어 변환

#include <string>
#include <vector>
#include <iostream>
#include<queue>
using namespace std;
int visit[51] = { 0, };// 중복 방지를 위한 배열
int flag = 0;
struct Data {
	string word;
	int cnt;
};
int solution(string begin, string target, vector<string> words) {
	int answer = 0;
	for (int i = 0; i < words.size(); i++) {// target값이 만약에 words에 없으면 바로 0리턴
		if (target == words[i]) {
			flag = 1;
		}
	}
	if (flag == 0)return 0;
	flag = 0;

	queue<Data>q;
	q.push({begin, 0});

	while (q.size()!=0) {//전체 탐색시작
		Data c = q.front(); q.pop();
		if (c.word == target) {
			answer = c.cnt;
			break;
		}
		for (int i = 0; i < words.size(); i++) {
			Data n=c;
			int wordSameCnt = 0;
			for (int j = 0; j < words[i].size(); j++) {//몇개의 알파벳이 다른지 검사
				if (c.word[j] != words[i][j]) {
					wordSameCnt++;
				}
			}
			if (wordSameCnt == 1) {//단어에서 알파벳 한개가 다른경우 푸시
				if (visit[i] == 0) {
					visit[i] = 1;
					n.word = words[i];
					n.cnt++;
					q.push(n);
				}

			}
		}
		
	}
	
	return answer;
}
int main(void) {
	//cout<<solution("hit", "cog", { "hot","dot","dog","lot","log","cog" })<<endl;
	cout<<solution("hit", "cog", { "hot", "dot", "dog", "lot", "log" });
	return 0;
}

큐를 이용한 bfs를 알고 있으면 쉬운 문제라고 생각한다. 

문제의 효율을 좀더 올리기위해 처음에 target으로 하는 것이 words에 포함되지 않으면 큐를 돌리지 않고

바로 0을 리턴했다.

 

각 단어에서 알파벳이 1개가 다른경우 그 단어로 대체 되고 거기에서 target으로 하는 단어까지의 방법의 최소를 

구하라고 하길래 단번에 bfs로 풀어야겠다고 생각했다.

 

그리고 전체 words를 다돌리면서 현재 값이랑 그 words 안에 단어중 알파벳이 하나 다른것을 찾고

그 단어를 푸시하면서 큐를 돌렸다. 그러다가 target이 되면 바로 큐를 빠져나오도록 설계했다.

 

그렇게 한번 풀어보면 될것같다.