[Programmers] 단어 변환

안녕하세요. 이번 포스팅에서는 Programmers 단어 변환 문제를 풀어보도록 하겠습니다.

 

해당 문제는 

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

코딩테스트 연습 - 단어 변환

 

위 링크에서 확인하실 수 있습니다.

 

전형적인 BFS문제입니다. 각 단어를 그래프의 노드로 생각하고, 현재 단어에서 다음 단어로 변환되는 과정이 모두 1이라는 cost가 필요하므로 이 문제는 가중치가 같은 최단거리 문제로 추상화할 수 있습니다.

 

queue를 사용하여, queue에서 첫 원소를 뽑고 다음에 갈 수 있는 word를 찾습니다. for loop를 words의 크기만큼 돌면서, 

 

방문이 되지 않고

현재 단어에서 하나 이하로 바꿀 수 있는 단어

 

를 찾아서 다음 원소로 넣어주시면 됩니다. 

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;

bool visited[51];
bool check(string cur, string next) {
    int ret = 0;
    for(int i = 0; i < cur.size(); i++) if(next[i] != cur[i]) ret++;

    return (ret<=1);
}
int solution(string begin, string target, vector<string> words) {
    int answer = 0;

    queue<pair<string, int>> q;
    q.push({begin, 0});

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