[프로그래머스 - 단어 변환] BFS C++

 

level3 지만 bfs로 간단하게 해결할 수 있는 문제였다. 오히려 level2보다 더 쉬운거 같기도 하고 ,.?

 

dog -> dot 

처럼 한 char만 바꿀 수 있다. 주어진 words의 문자들의 길이는 모두 동일하다고 조건이 주어졌기 때문에 단순히 두 문자열을 앞에서부터 비교하여 다른 char가 하나만 있을때 변환이 가능하도록 한다.

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <map>
#include <string.h>

using namespace std;
bool able = false;
queue <pair<string , int>> q;
map <string, int> visit;

int compchar(string a, string b){
    int len = a.length();
    int cnt =0;
    for(int i=0;i<len;i++){
        if(a[i] != b[i])
            cnt++;
    }
    if(cnt == 1) return 1;
    else return 0;
}
int solution(string begin, string target, vector<string> words) {
    for(int i=0;i<words.size();i++){
        visit[words[i]] = 0;
        if(words[i] == target){
            able = true;
        }
    }
    if(!able){
        return 0;
    }
    //words에 없다면 변환 불가능
    
    q.push({begin,0});
    visit[begin] = 1;
    
    while(!q.empty()){
        string cur = q.front().first;
        int level = q.front().second;
        q.pop();
        
        if(cur == target){
            return level;
        }
        
        for(int i=0;i<words.size();i++){
            string next = words[i];
            if(visit[next]==0 && compchar(cur,next) == 1){
                visit[next] =1;
                q.push({next, level+1});
            }
        }
    }
}

 

queue에는 <string, int> pair을 넣어 현재 변환된 문자열과, 몇단계를 거쳤는지를 저장한다. 

 

보통 bfs문제 풀이에서는 정수로 노드가 주어져서 visit을 배열로 선언했었다. (visit : 이미 방문한 문자열인지 확인하기 위해 필요)

이 문제에선 문자열을 처리하기 위해 map<string,int> 로 방문 여부를 저장했다.