[프로그래머스] Lv.3 단어 변환 c++

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

프로그래머스

 

주어진 단어 begin에서 target으로 변환하는 가장 짧은 과정을 찾는 문제입니다. 변환 과정에서는 다음 규칙을 따라야 합니다:

1. 한 번에 한 개의 알파벳만 변경할 수 있습니다.
2. 변경된 단어는 반드시 주어진 단어 목록(words)에 포함되어 있어야 합니다.

문제 조건

• 모든 단어는 소문자 알파벳으로 이루어져 있으며, 길이는 동일합니다.
• 변환 과정에서 target 단어로 변환할 수 없으면 0을 반환합니다.

 

풀이 방법

이 문제는 BFS로 풀 수 있습니다.

BFS는 최단 경로를 찾는 데 효과적이기 때문에 begin에서 target까지의 최소 변환 단계를 구하는 데 적합합니다.

 

우선, queue 자료구조를 사용하여 words를 탐색합니다. 큐에는 현재 단어와 변환 횟수를 저장합니다. 탐색 과정에서 현재 단어와 다음 단어의 알파벳 차이가 한 글자인 경우, 그리고 해당 단어를 아직 방문하지 않은 경우, 그 단어를 큐에 추가합니다. 단어를 큐에 추가하면서 변환 횟수(index)를 1 증가시켜 저장합니다. 또한, 중복 방문을 방지하기 위해 방문한 단어는 visited 배열을 통해 관리합니다.

 

만약 현재 단어가 target과 같아지면 그 즉시 현재 변환 횟수(index)를 반환합니다. 이 과정을 반복하다 큐가 비거나 target에 도달하지 못하면 변환할 수 없는 경우이므로 0을 반환합니다.

 

풀이 코드

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

using namespace std;

bool visited[50];
int solution(string begin, string target, vector<string> words) {

    if(find(words.begin(), words.end(), target) == words.end()) return 0;
    
    queue<pair<string, int>> q;
    q.push({begin, 0});
    while(!q.empty()){
        string current_name = q.front().first;
        int index = q.front().second;
        q.pop();
        
        if(current_name == target) return index;
        
        for(int i=0; i<words.size(); i++){
            int diff = 0;
            for(int j=0; j<words[i].size(); j++){
                if(words[i][j] != current_name[j]) diff++;
            }
            if(diff == 1 && !visited[i]){
                q.push({words[i],index+1});
                visited[i] = true;
            } 
        }
    }
    return 0;
}