(프로그래머스 C++) 단어 변환

링크 : programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

분류 : 깊이/너비 우선 탐색 (DFS/BFS)

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

using namespace std;

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    queue<pair<string,int>> q;
    q.push(make_pair(begin,0));
    while(!q.empty()){
        string s1 = q.front().first;
        int num = q.front().second;
        q.pop();
        if(s1==target){
            return num;
        }
        for(int i=0; i<words.size(); i++){
            int cnt = 0;
            for(int j=0; j<words[i].size(); j++){
                if(s1[j]==words[i][j]) cnt++;
            }
            if(cnt==words[i].size()-1){
                q.push(make_pair(words[i],num+1));
                words[i] = "";
            }
        }
    }
    
    return answer;
}

전형적인 BFS문제로, 큐의 쌍을 만드는 법만 잘 활용하면 문제없이 풀 수 있다.