[프로그래머스] 단어 변환 (c++) string, bfs

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

프로그래머스

풀이 방법

변환이 가능한지 확인할 수 있는 함수가 필요하다 이를 위해 두 단어의 스펠링 개수 차이가 1이면 가능하다고 판단하는 canChange함수를 작성했다.
그 후 일반적인 bfs함수를 통해 tartget 단어가 될 때까지 수행했다.

 

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

using namespace std;

bool canChange(string str1, string str2) { // 글자 변경 가능 확인
    int n = str1.length();
    int diff = 0;
    for (int i = 0;i < n;i++) {
        if (str1.at(i) != str2.at(i)) {
            diff++;
        }
    }
    if (diff == 1) { // 변경 가능
        return true;
    } 
    else { //변경 불가능
        return false;
    }
}

int bfs(string begin, string target, vector<string> words) {
    queue<pair<string, int>> q;
    q.push(make_pair(begin, 0)); // 다음 단더, 횟수 저장
    vector<int> visited(words.size(), 0); // 방문 배열 초기화
    
    while(!q.empty()) {
        string next = q.front().first;
        int cnt = q.front().second;
        q.pop();
        for (int i = 0;i < words.size();i++) {
            if (visited[i] == 0 && canChange(next, words[i])) { // 변경 가능하다면
                if (words[i] == target) {
                    return cnt+1;
                }
                visited[i] = 1;
                q.push(make_pair(words[i], cnt+1));
                
            }
        }
    }
    return 0; // 정답이 없는 경우
}

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