[C++] 프로그래머스 lv3 단어 변환 (BFS)

문제

프로그래머스 DFS/BFS - 단어 변환

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

프로그래머스

 

문제 풀이

단어 변환을 위한 '최소 횟수'를 구하기 위해 bfs 사용 (최단거리와 동일한 개념으로 접근)

bfs를 돌며, 현재 비교하는 대상 단어와 변환 횟수를 pair로 묶어서 반복

문자열간 비교를 이렇게밖에 못하나? 고민했으나..

find 함수라는 것도 서치해봤지만 오히려 더 복잡해질거라 판단.

 

풀이 코드

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

using namespace std;

int answer = 0;
queue<pair<string,int>> q;
bool visit[50];

int bfs( vector<string> words, string target ){ //최소단계 return하는 bfs
    while(!q.empty()){
        string now=q.front().first;
        int cnt=q.front().second;
        q.pop();  
        
        for(int i=0;i<words.size();i++){
            // 비교한적 없는 n번째 단어 탐색
            if(visit[i]) continue;    
            
            // n번째 단어로 비교
            string cmp=words[i];
            
            // 두 단어간 서로 다른 문자일때 카운트
            int diff=0;
            
            for(int j=0;j<cmp.size();j++){
                // 두개 이상 다른 문자면 더 확인할 필요 없음
                if(diff>=2) break;
                if(now[j]!=cmp[j]) diff++;
            }
            if(diff==1){ // 한글자만 바뀌면 동일한 문자열 존재하는지
                if(cmp.compare(target)==0) // 정답인지
                    return cnt;
                q.push({cmp,cnt+1});
                visit[i]=true;
            }
        }
    }
    return 0; // 큐 다 돌았는데 동일한 문자열로 될 수 없을때
}

int solution(string begin, string target, vector<string> words) {
    q.push({begin,1});
    answer=bfs(words,target);
    return answer;
}