[Programmers] 단어 변환

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

코딩테스트 연습 - 단어 변환 | 프로그래머스

 

이 문제는 그래프를 따로 만들 수 있는지 없는지가 중요하다.

 

- 풀이 방법

1. 그래프를 따로 만들고 BFS로 풀었다.

 

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

using namespace std;

int visit[52];

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    vector<string> new_words;
    vector<vector<int>> vec(words.size() + 1);
    
    //하나로 합쳐줌(그래프를 만들어준다)
    new_words.push_back(begin);
    for(int i=0; i<words.size(); i++) {
        new_words.push_back(words[i]);
    }
    
    for(int i=0; i<new_words.size() - 1; i++) {       
        string temp = new_words[i];
        
        for(int j=i+1; j<new_words.size(); j++) {
            string temp1 = new_words[j];
            int dif_cnt = 0;
            
            for(int k=0; k<temp1.length(); k++) {
                if(temp[k] != temp1[k]) {
                    dif_cnt += 1;
                }
            }
            if(dif_cnt == 1) {
                vec[i].push_back(j);
                vec[j].push_back(i);
            }
        }    
    }
    
    if(begin != target) {
        queue<int> q;
        q.push(0);
        visit[0] = 1;
        
        while(!q.empty()) {
            int from = q.front();
            string cur = new_words[from];
            q.pop();
            
            bool flag = false;
            for(int i=0; i<vec[from].size(); i++) {
                int to = vec[from][i];
                if(visit[to] == 0) {
                    visit[to] = visit[from] + 1;
                    
                    if(new_words[to] == target) {
                        flag = true;
                        answer = visit[to] - 1;
                        break;
                    }
                    q.push(to);   
                }
            }
            if(flag) break;
        }
    }
    
    return answer;
}