🌞문제

🌞접근법

조건1. begin -> target으로 단어를 변환해야 한다.
조건2. 한번에 한개의 알파벳만 바꿀 수 있다.
조건3. words에 있는 단어로만 변환 할 수 있다.
조건4. 알파벳은 소문자로만 이루어져 있다.
조건5. 단어의 길이는 3~10 이다.
조건6. words에는 3~50개의 단어가 있고, 중복은 없다.
조건7. begin과 target은 같지 않다.
조건8. 변환이 불가능한 경우 0을 return 한다.

구해야 하는 값 : 최소 몇단계의 과정을 거쳐 begin이 target으로 변환 할 수 있는지 return 하여라.

먼저 words에서 변환이 가능한 결과 값이 있는지를 확인한다.
그 값으로 변환한 기억이 있다면 그 값은 제외하고 다음 값을 확인한다.
(변환 할 수 있는 값이 없으면 0으로 return 한다.)

위와 같은 방식으로 방문을 하다가, target이 나오면 count 값을 return 한다.
이외에 모두 방문을 하였는데 target 값이 나오지 않는다면 0을 return 한다.

위와 같은 경우는 하나의 방문 방법이 될 것이다.
모든 경우의 수를 찾기에는 너무 많은 시간이 소요된다.

그렇다면 하나만 다른 경우는 어떻게 찾아야 하는가?
한번 찾을떄 최대 10번을 본다. 10*50 = 500, 한번 찾는데 최대 500의 시간이 걸린다.
모든 방법을 탐색하려면, 이것을 50번 해야하니 25000의 시간이 든다.

이러한 방법은 여러가지가 있기 떄문에 더 걸릴 것이다.

이를 해결하기 위해서는 bfs 방식을 사용해야 한다.

begin을 기준으로 트리를 만든다 하자. 여기서 자식들은 words의 요소들이 될 것이다.
hit를 기준으로 했을 때,
자식은 hot, dot, dog, lot ,log ,cog일 것이다.
여기서 이 트리에서 hit가 자식으로 변환 할 수 있는지를 확인한다.
만약에 된다면, 큐를 하나 생성하여 큐에 words에서 자신을 제외한 나머지 요소들을 다시 큐에 삽입한다.
이때 깊이 탐색에 관하여 visit 배열을 유지 할 필요가 있다. 한 방법에 대한 이전에 방문한 요소는 방문해서는 안되기 때문이다.

이 과정에서 target과 같은지를 계속 확인해주어야 한다.
그래서 만약에 같은 경우가 나오면 바로 count 값을 return하고 종료해주고, 그렇지 못하면 모든 경우를 탐색하고 0을 return할 것이다.

🌞풀이

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

using namespace std;

int n;
queue<int> q;
queue<vector<int>> visit;
string target;
vector<string> words;
string g_begin;

int bfs()
{
    vector<int> _visit;
    int idx = q.front();
    q.pop();
    
    string x;
    
    if(idx == -1)
    {
        _visit.resize(words.size(),0);
        x = g_begin;
    }
    else
    {
        _visit = visit.front();
        visit.pop();
        x = words[idx];
    }


    for(int i=0; i<words.size() ;i++)
    {
        if(_visit[i] == 0)
        {
            vector<int> tmp_visit = _visit;
            int word_cnt=0;
            for(int j=0;j<n;j++)
            {
                if(x[j] != words[i][j]) word_cnt++;
                
            }
            
            if(word_cnt == 1)
            {
                if(words[i] == target)
                {
                    int cnt=0;
                    for(int k=0;k<words.size();k++)
                    {
                        if(tmp_visit[k] == 1) cnt++;
                    }
                    
                    return cnt+1;
                }
                
                q.push(i);
                tmp_visit[i] = 1;

                visit.push(tmp_visit);

                
            }

        }
    }
    
    if(q.empty())
    {
        return 0;
    }
    else
    {
        return bfs();
    }
}

int solution(string _begin, string _target, vector<string> _words) {
    int answer = 0;
    g_begin = _begin;
    target = _target;
    words = _words;
    n = g_begin.length();
    q.push(-1);
    
    return answer = bfs();
}