프로그래머스 단어 변환

 

 

이전 했던 풀이들에 너무 사로잡혀 있지 않아도 된다는 생각이 든 게,

이번에 depth를 계산함에 있어서, 첫 시작부터 visit처리를 해주지 않는 풀이 상에서 예전처럼 그대로 구현할 수는 없었다.

 

여태까지는 계속

depth[new] = depth[prev] + 1;

이런식으로 진행했고, 물론 이를 visit으로 한번에 하기도 했는데

 

결국 기준이 되는 첫 인자의 원소가 있어야 하는데, 그건 문제에서 배열 내에 속하지 않기 때문에 이렇게 하기가 어려웠다.

 

그래서 생각의 전환으로

 

어차피 que에 넣은 값을 기준으로 흐름이 움직이게 되는데, 넣을 때 depth값도 같이 넣으면 되지 않을까 라는 생각이었다.

queue<pair<string, int>> que; // 넣으려는 문자열, depth

이런식으로 말이다.

 

 

그렇게 해서 풀 수 있었고, 다른 사람의 풀이를 보니 나와같이 이러한 방식으로 푼 것을 알 수 있었다.

아래는 다른 사람의 풀이다.

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

using namespace std;

int visited[50];

int possible(string a, string b)
{
    int i;
    int cnt = 0;

    for(i=0;i<a.length();i++)
    {
        if(a[i] != b[i]) cnt++;
    }

    if(cnt==1) return 1;
    else return 0;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    queue<pair<string,int>> Q;
    int i;
    string temp;
    int num;

    Q.push(make_pair(begin,0));
    while(!Q.empty())
    {
        temp = Q.front().first;
        num = Q.front().second;
        Q.pop();

        if(temp.compare(target) == 0)
        {
            answer = num;
            break;
        }

        for(i=0;i<words.size();i++)
        {
            if(visited[i]) continue;
            if(possible(temp, words[i]))
            {
                visited[i] = 1;
                Q.push(make_pair(words[i],num+1));
            }
        }
    }

    return answer;
}

 

 

그리고 아래는 내 풀이다.

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

// 가장 짧은 -> bfs

using namespace std;

int bfs(string start, string end, vector<bool>& visit, vector<string>& words, int n, int ln) {
    
    queue<pair<string, int>> que; // string, depth
    
    que.push({start, 0});
    // start는 words 내에 없으므로, visit 처리 안해줌.
    
    while(!que.empty()) {
        
        
        string now = que.front().first;
        int dep = que.front().second;
        
        if(now == end)
            return dep;
        
        que.pop();
        
        
        for(int i = 0; i < n; i++) {
            
            
            if(!visit[i]) {
                // 방문 아직 안한 것 중에.
                
                int cnt = 0;
                for(int j = 0; j < ln; j++) {
                    
                    if(words[i][j] != now[j])
                        cnt++;
                    
                }
                
                if(cnt == 1) {
                    
                    // 한 글자가 다르다.
                    que.push({words[i], (dep + 1)});
                    visit[i] = true;
                    
                    
                }
                
                
            }
            
            
        }
        
        
    }
    
    return 0;
    
}


int solution(string begin, string target, vector<string> words) {
    int n = words.size();
    
    vector<bool> visit(n, false);
    
    return bfs(begin, target, visit, words, n, begin.length());

}

 

확실히 기업 코딩테스트를 준비하려면, 프로그래머스 기반의 환경과 입출력 방식에 익숙해지기 위해

프로그래머스를 문제풀이 사이트로 애용해야 겠다는 사실을 느끼고 있다.