프로그래머스/lv3/43163. 단어 변환

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

using namespace std;

bool v[50];

int check(string a, string b) {
    int count = 0;
    for (int i = 0; i < a.size(); i++)
        if (a[i] != b[i]) count++;
    return count == 1 ? 1 : 0;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    queue<pair<string, int>> q;
    int num;

    q.push(make_pair(begin, 0));
    while (!q.empty()) {
        string tmp = q.front().first;
        int tmpCnt = q.front().second;
        q.pop();

        if (tmp == target) return tmpCnt;

        for (int i = 0; i < words.size(); i++) {
            if (v[i]) continue;

            if (check(tmp, words[i])) {
                v[i] = 1;
                q.push(make_pair(words[i], tmpCnt + 1));
            }
        }
    }

    return 0;
}

BFS를 로직을 이용해 while문을 돌면서 String(문자열), int(탐색횟수) pair형태로 돌려준다.
q가 empty가 될 때 까지 반복하며 tmp, tmpCnt로 문자열과 탐색횟수를 저장하고, target과 일치하다면 탐색횟수를 return한다.

핵심로직은 한 글자만 달라야 Queue에 push하는 것이다. 그래서 따로 check함수를 만들었다. 그리고 일반적인 BFS와 같이 visited배열을 만들어 방문한 곳을 체크했다.

BFS,DFS 그래프 쪽 알고리즘이 약하다. 이런 종류의 문제를 많이 풀지 않아서 어려운 면이 있는 것 같다.