lv 3) 단어 변환

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=cpp

프로그래머스

 

BFS 풀이

#include <string>
#include <vector>
#include<queue>
//bfs 로 그래프 
// used 통해 한번 진행한거 다음에 진행하지 않게. -> bfs라 used 할 필요가없음. dfs였으면 해야함.

using namespace std;

struct node{
    string str;
    int lv;
};
bool IsChange(const string& base, const string& tar){
    int cnt = 0;
    for(int idx = 0; idx < base.size(); ++idx){
        if(base[idx] != tar[idx]){
            cnt++;
        }
    }
    if(cnt == 1)return true;
    return false;
}
int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    bool isExist = false;
    for(int idx = 0; idx < words.size();++idx){
        if(target == words[idx]){
            isExist = true;
            break;
        }
    }
    if(isExist == false) return 0;
    
    queue<node> q;
    q.push({begin, 0});
    while(!q.empty()){
        node front = q.front();
        q.pop();
        //1개 단어 차이 찾아서 q에 push.
        for(int idx = 0; idx < words.size(); ++idx){
            if(IsChange(front.str, words[idx]) == true){
                q.push({words[idx], front.lv+1});
                if(words[idx] == target){
                    return front.lv+1;
                }
            }
        }
    }
}

 

풀이 방식

 

하나의 알파벳으로만 변경 가능한 조건이며 이러한 조건으로 begin에서 target까지 가는데 몇 번 단어를 거치는지 구하는 문제.

bfs 통해서 현재 노드(front)의 단어와 하나의 알파벳만 다른 words 리스트에 후보가 있는지 체크(IsChange) 한다. 있다면 q에 push 하며 lv + 1 (몇 번 경유하는지, 실제 answer 역할) 을 추가한다.

이렇게 계속 진행하다 target 단어를 만나면 해당 lv을 리턴한다.

아예 target값이 word 리스트에 없을 수 있기에 사전에 검사하며 가지치기한다.

 

 

DFS 풀이

#include <string>
#include <vector>
#include<iostream>
using namespace std;

int mini = 999;
vector<string> wordsCp;
vector<int> visited;
bool IsCheck(const string & begin, const string& word){
    int cnt = 0;
      for(int y = 0; y < begin.size();++y){
          if(begin[y] != word[y]){
              cnt++;
          }
      
    }
    if(cnt ==1)return true;
    return false;
}
void dfs(string begin, const string& target, int lv){
    if(begin == target) {
        if(mini > lv) {
            mini = lv;
        }
        return;
    }
    for(int idx = 0; idx < wordsCp.size(); ++idx){
        if(visited[idx] ==0 && IsCheck(begin, wordsCp[idx])){
            visited[idx] = 1;
            dfs(wordsCp[idx], target, lv+1);
            visited[idx] = 0;
        }
    }
}
void init(const vector<string>& words){
    wordsCp = words;
    for(int idx = 0; idx < words.size(); ++idx){
        visited.push_back(0);
    }
}
int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    bool isExist = false;
    for(int idx = 0; idx < words.size(); ++idx){
        if(target == words[idx]){
            isExist = true;
            break;
        }
    }
    init(words);

    if(isExist == false)return 0;

    dfs(begin, target, 0);
    return answer = mini;
}

 

 

TODO: 최단경로 알고리즘으로도 가능하다 함. 이참에 최단경로 관련 알고리즘들(플루이드/크루스칼/다익스트라/A*) 좀 공부하고 풀어보기