9) 프로그래머스 Lv3 - 단어 변환

<문제>

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

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

BFS, DFS 모두 가능한 문제. 하지만 나는 BFS가 더 좋아서 BFS했음 ㅎㅎㅎㅎㅎㅎ

 

<코드>

#include <queue>
#include <string>
#include <vector>

using namespace std;

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    int flag = 0;
    for(int i = 0; i < words.size(); i++){
    	if(target == words[i]) {
    		flag = 1;
    		break;
		}
	}
	
	if(flag == 0) {
		return answer;
	}
	
	int lnth = begin.length();
	bool check[50] = {0, };
	
	queue<string> q;
	q.push(begin);
	
	while(!q.empty()) {
		int size = q.size();
		for(int i = 0; i < size; i++) {
			begin = q.front();
			q.pop();
			if(begin == target) {
				return answer;
			}
			for(int j = 0; j < words.size(); j++) {
				if(check[j] == 0) {
					for(int k = 0; k < lnth; k++) {
						flag = 0;
						for(int m = 0; m < lnth; m++) {
							if(m != k) {
								if(words[j][m] != begin[m]){
									flag = 1;
									break;
								}
							}
						}
						if(flag == 0) {
							q.push(words[j]);
							check[j] = 1;
						}
					}
				}
			}
		}
		answer++;
	}
}

다른 아이디어가 있으면 더 간단해지고 시간도 빨라질 것 같은 문제.

 

target이 words vector에 없으면 그냥 바로 끝낸다. (flag사용함)

그 후에는 bfs하던대로 문제를 푼다.

Queue에 넣는 과정을 다음과 같은 방법으로 풀었다.

 

1. check를 확인하여 한번도 큐에 들어간 적이 없어야한다. ( 안되면 테스트 3 통과할 수 없다. - check[j] == 1이라고 썼었음... ㅎㅎㅎ..... 이걸 찾느라 오래걸림 ...ㅠㅠㅠㅠㅠ 바보지 바보야......)

2. 한 단어만 바꿀 수 있으면 되니까 k번째만 빼놓고 string값 비교를 한다. (for k)

2-1. 만약 둘다 같으면 flag = 0. 큐에 들어가면서 check값이 변한다.(for m)

2-2. 다른곳이 두곳 이상이면 바로 다음 단어로.

3. begin과 target이 같으면 retrun 해준다.

 

어떻게 해야지는지 솔직히 감이 잡히지 않았다.

이 방법을 생각했을 때는 시간 초과 될거 같은데... 싶기도 했다.

근데 됬다. 이럴때 기분이 너무 좋다 ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ

 

끝!

 

<Testing 코드>

#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    int flag = 0;
    for(int i = 0; i < words.size(); i++){
    	if(target == words[i]) {
    		flag = 1;
    		break;
		}
	}
	
	if(flag == 0) {
		return answer;
	}
	
	int lnth = begin.length();
	bool check[50] = {0, };
	
	queue<string> q;
	q.push(begin);
	
	while(!q.empty()) {
		int size = q.size();
		for(int i = 0; i < size; i++) {
			begin = q.front();
			q.pop();
			if(begin == target) {
				return answer;
			}
			for(int j = 0; j < words.size(); j++) {
				if(check[j] == 0) {
					for(int k = 0; k < lnth; k++) {
						flag = 0;
						for(int m = 0; m < lnth; m++) {
							if(m != k) {
								if(words[j][m] != begin[m]){
									flag = 1;
									break;
								}
							}
						}
						if(flag == 0) {
							q.push(words[j]);
							check[j] = 1;
						}
					}
				}
			}
		}
		answer++;
	}
}

int main(void) {
	vector<string> words;
	int N;
	string s, begin, target;
	cin >> N;
	
	cin >> begin >> target;
	
	for(int i = 0; i < N; i++) {
		cin >> s;
		words.push_back(s);
	}
	
	cout << solution(begin, target, words);

	return 0;
}

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ예전엔 보지도 못하는 Lv.3 문제를 푸는데 실력이 느는게 보였다. 기분이 좋다!!!!

내가 이겨?!?!?!? 엉!?!??!