프로그래머스 : 단어변환(C++, Lv.3, BFS)

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

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

처음에는 dfs로 풀려 했는데 제대로 풀지도 못한 것 같고 우선 간단한 테스트 만으로도 시간 초과가 나서 bfs로 풀었다.

이번에도 시간초과가 나는 것을 막기 위해 한 번 탐색한 문자열은 큐에 넣지 않고 탐색했다.

레벨3인데 혼자 고민해서 어떻게든 풀 것 만으로도 너무 감사하다...

 

소스코드

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

using namespace std;
int ch[52];
int bfs(string begin, string target, vector<string> words) {
    //현재 문자열과 과정 횟수를 담는 큐 선언
    queue<pair<string,int>> q;        
    q.push(make_pair(begin,0));
    
    int diff;
    
    while(!q.empty()) {
        pair<string,int> p = q.front();
        //현재 문자열과 타겟이 같다면 횟수 반환
        if(p.first == target) return p.second;
        
        q.pop();
        //words 문자열들과 비교해 한글자만 다르다면 큐에 삽입
        for(int i = 0; i < words.size(); i++) {
            diff = 0;
            for(int k = 0 ; k < target.length(); k++) {
                if(p.first[k] != words[i][k]) diff++;
            }
            if(diff == 1 && ch[i] == 0) {
                ch[i] = 1;
                q.push(make_pair(words[i], p.second+1));   
            }
        }
    }
    return 0;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    answer = bfs(begin, target, words);
    
    return answer;
}