[코딩테스트] [프로그래머스] 단어 변환

문제

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

---

풀이

1. source 문자열과 target 문자열을 비교한다고 가정하자. 1개의 문자 빼고 모두 같으며 한번도 확인하지 않은 문자열이라면 source 문자열은 target 문자열로 변환될 수 있다.
   1-1. 문자열을 비교할 수 있는 canChange 함수를 만든다.

2. 해당 과정을 words 벡터를 순회하며 반복하고, 만약 현재 문자열이 최종 문자열과 같다면 변환 횟수를 반환한다.
   2-1. 이때, bfs용 큐에는 현재 문자열과 변환 횟수를 담을 수 있도록 pair<string, int>를 자료형으로 사용한다.

---

코드

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

using namespace std;

bool canChange(const string& source, const string& target)
{
    int diff = 0;
    for(int i=0; i<source.size(); i++)
    {
        if(source[i] != target[i])
            diff++;
        if(diff > 1)
            return false;
    }
    
    return diff == 1;
}

int solution(string begin, string target, vector<string> words) 
{    
    vector<bool> visited(words.size(), false);
    
    queue<pair<string, int>> bfs;
    bfs.push({begin, 0});
    
    while(!bfs.empty())
    {
        string currentString = bfs.front().first;
        int currentLength = bfs.front().second;
        bfs.pop();
        
        if (currentString == target)
            return currentLength;
        
        for (int i=0; i<words.size(); i++)
        {
            if (!canChange(currentString, words[i]) || visited[i])
                continue;
            
            visited[i] = true;
            bfs.push({words[i], currentLength + 1});
        }
    }
    
    return 0;
}