아래 모든 문제들은 프로그래머스에서 제공 되는 문제를 이용하였습니다, 감사합니다.

• 틀린거 없음!

단어 변환

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

• 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
• 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

풀이

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int dif_count(string s1, string s2)
{
    int value = 0;
    for(int i = 0; i < s1.size(); i++)
    {
        if (s1[i] != s2[i])
            value++;
        if (value == 2)
            break;
    }
    return value;
}

int bfs(string begin, string target, vector<string> words, vector<int> visit)
{
    pair<string, int> tmp(begin, 0);
    queue<pair<string, int>> q;
    q.push(tmp);

    while(!q.empty())
    {
        tmp = q.front();
        q.pop();
        if(tmp.first == target)
            return tmp.second;
        for(int i = 0; i < words.size(); i++)
            if(1 == dif_count(tmp.first,words[i]) && visit[i] == 0)
            {
                visit[i] = 1;
                q.push(pair<string, int>(words[i], tmp.second + 1));
            }
    }
}

int solution(string begin, string target, vector<string> words) {
    vector<int> visit (words.size(), 0);
    if (!(*find(words.begin(), words.end(), target) == target))
        return 0;
    return bfs(begin, target, words,visit);
}

설명

• 우선, 목적 값이 없으면 0을 반환해주라고 해서 find를 해서 리턴 0을 해주었다.(find를 하게되면 해당 값이 있는 주소값을 반환해준다.)
• 그리고 bfs를 이용해서 풀었다.코드는 간결햇다.
• push해준 값들을 하나씩 뺴면서 1글자만 차이나는 값들을 다시 푸시해주고 확인하는 형태다.
• 그리고 방문했던 곳들은 다시 방문하면 탐색 횟수만 늘어나므로 visit를 통해 제거해주었다.