[프로그래머스] 단어 변환 C++

 

 

 

 

 

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

프로그래머스

 

이번 문제는 BFS/DFS 문제였습니다.

 

 

 

 

 

📝 문제 풀이

1. words에 target이 없으면 곧바로 종료

2. words에서 begin과 한 개의 알파벳만 다른 단어를 모두 큐에 삽입하고 방문 표시

3. 큐에 넣은 단어와 target이 같으면 ➡️ answer과 현재까지의 변환 단계 중 더 작은 값으로 answer 갱신

 

 

 

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 50

using namespace std;

int answer = MAX + 1;
bool visited[MAX];
queue<pair<string, int>> q;

// 한 개의 알파벳만 다른지 비교하는 함수
bool compareWords(string begin, string word) {
    int cnt = 0;
    
    for (int i=0; i<word.length(); i++) {
        if (begin[i] == word[i]) {
            cnt += 1;        
        }
    }
    
    if (cnt == word.length() - 1) return true;
    return false;
}

void BFS(string begin, string target, vector<string> &words) {
    int len = words.size();
    q.push({begin, 0});
    
    while (!q.empty()) {
        string word = q.front().first;
        int level = q.front().second;
        q.pop();
        
        if (word == target) {
            answer = min(answer, level);
        }
        
        for (int i=0; i<len; i++) {
            bool isOk = compareWords(word, words[i]);
            if (visited[i] || !isOk) continue;
            
            q.push({words[i], level + 1});
            visited[i] = true;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    vector<string>::iterator iter;
    iter = find(words.begin(), words.end(), target);
    
    // words에 target이 없으면 0 반환
    if (iter == words.end()) return 0;
    
    BFS(begin, target, words);
    
    return answer;
}

 

프로그래머스 - 결과 화면