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

문제 요약

1. 길이가 [3,10]인 단어 start가 주어집니다.
2. start와 길이가 같은 단어 [3,50]개의 배열인 words가 주어집니다.
3. start에서 target을 만드는 데 필요한 변환 횟수의 최솟값을 구하세요.
   단, 변환은 한번에 하나의 문자만 바꾸었을 때 words에 있는 단어인 경우만 가능합니다.

아이디어

dfs를 하면 맨 앞 자리에서만 dfs 하느라 다른 자리를 바꿔주는 경우들을 많이 못 볼 것같아서 bfs로 구현해주었다.
bfs를 하면 큐 상에서 레벨의 경계가 뚜렷하며 순차적으로 레벨이 증가한다는 점에서 level 혹은 depth 끝까지 가보는 dfs보다 최솟값을 빨리 찾을 수 있다는 힌트를 얻었다.
bfs 할 때 큐에 넣을 수 있는 것들은 words사전에서 한번도 bfs를 거쳐가지 않은 것들이었다.
문자열 완전탐색..? 문제의 경우 dfs가 많은데 bfs문제를 처음 만나봐서 즐겁게 풀었다.

삽질

한번 bfs를 했던 단어의 경우 일반적인 bfs알고리즘에 사용되는 visited 배열에 마킹을 해줬어야했는데 그러질 않아서 시간초과가 났었다.

코드

#include <string>
#include <vector>
#include<unordered_map>
#include<queue>
using namespace std;
struct qmem{
    string str;
    int l;
    qmem(string s, int ll){
        str = s; l= ll;
    }
};
int bfs(string begin, string target,unordered_map<string,int> s){
    queue<qmem> q;
    q.push(qmem(begin,0));
    int res = -1;
    while(!q.empty()){
        qmem cur = q.front();
        q.pop();
        if(cur.str == target){
            res = cur.l;
            break;
        }
        
        for(int i = 0;i<cur.str.size();i++){//한 글자씩 바꿔가며
            char ori = cur.str[i];
            for(char t = 'a';t<='z';t++){
                if(t == ori){
                    continue;
                }
                string child = cur.str;
                child[i] = t;
                unordered_map<string, int>::iterator it = s.find(child);
                if(it !=s.end()&&it->second==0){//사전에 있을 때, 한 번 들렀을 때만
                    q.push(qmem(child, cur.l+1));
                    it->second++;
                }
            }
        }
    }
    return res;
    
}


int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    unordered_map<string,int> s;
    for(int i = 0;i<words.size();i++){
        s.insert({words[i],0});//중복 없대서 걍 넣음
    }
    
    answer = bfs(begin,target, s);
    if(answer == -1){
        answer =0;
    }
    return answer;
}

여담

요즘 프로그래머스 레벨 3 문제를 곧잘 풀긴하는데... 이미 알고리즘이 정해진 이분탐색, 그래프 탐색, 그래프 알고리즘과 같이 코드를 외우고 있는 경우를 빼고 아이디어가 필요한 DP문제를 잘 못 풀고 시도조차 두려워한다는 게 좀... 그렇다. 이 문제만 해도 N으로 표현하기 DP문제를 풀다가 머리 식힐려고 도전한 거고... 예전에 방학마다 백준에서 DP 문제만 주구장창 풀면서 DP 감을 좀 잡아놨었는데 그게 끊긴 것이 너무 아쉽다...... << 이거 관련해선 할 얘기가 많다...