프로그래머스(깊이/너비 우선 탐색; 단어 변환) c++

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

using namespace std;

int diffCount(string a, string b)
{
    int diff = 0;
    for (int i = 0; i < a.size(); ++i)
    {
        if(a[i] != b[i]) diff++;
    }
    return diff;
}

int solution(string begin, string target, vector<string> words) {

    vector<bool> bvisited(words.size(), false);
    queue<pair<string, int>> q;
    q.push({begin, 0});
    
    while(!q.empty())
    {
        auto [currWord, count] = q.front();
        q.pop();
        
        if(currWord == target) return count;
        
        for(int i = 0; i < words.size(); ++i)
        {
            if(bvisited[i]) continue;
            if(diffCount(currWord, words[i]) > 1) continue;
            
            bvisited[i] = true;
            q.push({words[i], count +1});
        }
    }
    
    return 0;
}

 

해설:

begin과 target이 주어짐 words안에 begin과 똑같거나 한 글자 차이가 있는 단어들에 대하여 점진적으로 접근하여 target과 똑같은 단어를 찾는 것이다.

 

첫번째: bvisited(방문 검사), q(queue->#include <queue>, pair<string, int> ->마지막 문자, 카운트)를 선언 후 q에 begin과 0을 삽입

두번쨰: q.front()를 가져오고 pop() -> 무한 루프 방지, 먼저 진입하기전에 현재 단어와 target이 같은 경우에 count를 반환하게 해준다(이후에 있는 코드들을 통해 다시 while문 상단으로 올라가 검사하기 때문).

세번쨰: 반복문을 통해 방문한적이 있는지, diffCount 함수를 통해 현재 단어와 words[i]의 차이 수가 1 초과일 경우 건너뛴다.

그렇게 통과하면 true로 변환 후 q.push하여 기록을 남김, 이후 계속 반복 후 for문이 끝나면 두번쨰부터 세번째를 반복함.