C++ / 프로그래머스 / 단어 변환

문제

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

프로그래머스

 

문제풀이

최소 과정을 찾기 위해 queue를 이용했다.

queue에는 바꾼 단어, 바꾼 횟수를 저장한다.

이중 for문을 이용해 비교할 단어를 고르고, 단어를 문자로 쪼개서 현재 단어와 비교한다.

최소 과정을 찾아야 하므로 이미 고른 단어는 다시 못 고르도록 visit벡터를 추가로 이용했다.

같지 않은 부분이 1개라면 바꿀 수 있는 단어다.

바꿀 수 있는 단어가 target이라면 cnt + 1 값을 return한다.

그 외의 경우는 방문표시를 하고 큐에 바꾼 단어, cnt + 1을 넣어 push한다.

 

 

 

코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(string begin, string target, vector<string> words) {
    int answer(0), cnt(0), idx(0), idx2(0), sub(0);
    string str("");
    queue<pair<string, int>>q;
    vector<bool>visit(words.size(), false);

    q.push({ begin,0 });

    while (!q.empty()) {
        str = q.front().first;
        cnt = q.front().second;
        q.pop();
        for (idx = 0; idx < words.size(); ++idx) {
            if (visit[idx] == false) {
                sub = 0;
                for (idx2 = 0; idx2 < words[idx].size(); ++idx2) {
                    if (words[idx][idx2] != str[idx2]) {
                        sub++;
                    }
                }
                if (sub == 1) {
                    if (words[idx] == target) {
                        return cnt + 1;
                    }
                    else {
                        visit[idx] = true;
                        q.push({ words[idx], cnt + 1 });
                    }
                }
            }
        }
    }
    return 0;
}