99클럽 코테 스터디 33일차 TIL, 프로그래머스 / 단어변환

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

프로그래머스

 

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

using namespace std;

char alphas[] = {'a','b','c','d','e','f','g','h','i',
                'j','k','l','m','n','o','p','q','r',
                's','t','u','v','w','x','y','z'};

unordered_map<string, int> wordMap;

vector<string> changeWords(const string& origin, int idx)
{
    vector<string> nxtWords;
    nxtWords.reserve(origin.size());
    
    char originChar = origin[idx];
    string copy = origin;
    
    // 하나의 문자를 변환해서, 2개의 대상이 나올 수 있는 거
    // 아닌가 ?
    for (int cIdx = 0; cIdx < 26; ++cIdx)
    {
        if (alphas[cIdx] == originChar) continue;
        
        copy[idx] = alphas[cIdx];
        
        if (wordMap.find(copy) != wordMap.end())
            nxtWords.push_back(copy);
    }
    
    return nxtWords;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    vector<bool> visited;
    visited.resize(words.size(), false);
    
    for (int i = 0; i < words.size(); ++i)
        wordMap[words[i]] = i;
    
    // words 에 있는 내용들을 map(key:str,val:idx) 에 저장
    // 처음 시작부터 각 단어 1개씩 변경시키기
    // words 에 있다면 visit 처리하고 나오기
    // target 에 도달하면 answer
    queue<pair<string, int/*cnt*/>> q;
    q.push({begin, 0});
    // visited[]
    
    while(!q.empty())
    {
        pair<string, int> elem = q.front();
        q.pop();
        
        const string& curString = elem.first;
        
        if (curString == target)
            return elem.second;
        
        // 이미 visited 이면 continue
        int strIdx = wordMap[curString];
        // if (visited[strIdx]) continue;
        
        for (int i = 0; i < curString.size(); ++i)
        {
            vector<string> nxtWords = changeWords(curString, i);
            if (nxtWords.empty()) continue;
            for (const string& nxtWrd : nxtWords)
            {
                strIdx =  wordMap[nxtWrd];
                if (visited[strIdx]) continue;
                visited[strIdx] = true;
                q.push({nxtWrd, elem.second + 1});
            }
        }
    }
    
    return answer;
}

 

이 경우 3번 케이스에 대해서 유일하게 실패가 나온다.

일단 귀찮으니까 넘어가자..시간도 없고...