[코딩테스트C++] 단어 변환

오늘의 문제

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

단어 변환

나의 풀이

#include <string>
#include <vector>

using namespace std;

bool check[51] = {false, };
int answer = 51;

void dfs(string begin, string target, vector<string> words, int depth){
    for(int j=0;j<words.size();j++){
        if(check[j] == false){
            int same= 0;
            for(int i=0;i<begin.size();i++){
                if(begin[i] == words[j][i])
                    same ++;
            }
            if( same == begin.size()-1){
                if(words[j] == target){
                    answer = min(answer, depth+1);
                    return;
                }
                check[j] = true;
                dfs(words[j], target, words, depth+1);
                check[j] = false;
            }
        }
    }
}

int solution(string begin, string target, vector<string> words) {  
    dfs(begin, target, words, 0);
    if(answer == 51)
        answer = 0;
    return answer;
}

모범 답안

#include <string>
#include <vector>

using namespace std;

string targ;
vector<string> word;
int size;
int wordsize;
int answer;

void bfs(int n, string begin, vector<int> visited){
    if(begin.compare(targ)==0 && n < answer) answer = n;
    for(int i=0; i<size; i++){
        if(visited[i]==1) continue;
        int t = 0;
        for(int j=0; j<wordsize; j++){
            if(begin[j] != word[i][j]) t++;
            if(t>1) break;
        }
        if(t==1){
            visited[i]=1;
            bfs(n+1, word[i], visited);   
        }
    }

}

int solution(string begin, string target, vector<string> words) {
    answer = 999999999;
    size = words.size();
    wordsize = begin.length();
    targ = target;
    word = words;
    vector<int> visited(size,0);
    bfs(0, begin, visited);
    if(answer == 999999999) return 0;
    return answer;
}

배울 점

• dfs를 사용하는 문제는 여러갈래 길 중 하나를 선택해서 최선을 찾는 경우에 사용된다. 그게 보여서 dfs를 선택했다. 어제 풀었던 문제와 비슷하다 어제 풀어봐서 그런지 쉽게 작성할 수 있었다.
• 생각보다 테스트케이스를 만들어서 테스트해보는것이 쉽지않다. 어떤 입력을 넣어야하는지 헷갈려온다. 그래서 테스트를 하기위한 프로그램을 짜나보다

• 오 이사람은 다른 개수를 세었다. 이게 맞다. 다른개수를 세면 size를 찾아오는 번거로움이 없이 1<cnt 인지만 검사하면 된다. 똑똑하게 생각하자. 다만 이사람은 answer를 단어개수의 최대가 50인 문제에서 99999999라 하는 인간미를 보였다