프로그래머스 - 단어 변환 (C++)

문제 링크입니다. 카테고리가 DFS/BFS라서 힌트가 이미 주어지네요.?

프로그래머스

---

 

최소 또는 최단거리를 구하라고 할때는 bfs를 먼저 생각하면 좋습니다.

 

아래는 정답 코드이고 그 밑에 설명이 있습니다.

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

using namespace std;

int result = 500;
bool visit[50] = {};

struct State {
    string str;
    int count;
};

bool canJump(string a, string b) {
    int sz = a.size();
    int sum = 0;
    for(int i = 0; i < sz; i++) {
        if(a[i] != b[i]) sum++;
    }
    return sum == 1;
}

void bfs(string begin, string target, vector<string> words) {
    queue<State> q;
    q.push({begin,0});
    while(!q.empty()) {
        State current = q.front();
        q.pop();
        
        if(current.str == target) result = min(result, current.count);
        
        else {
            for(int i = 0; i < words.size(); i++) {
                if(visit[i]) continue;
                if(!canJump(current.str, words[i])) continue;
                q.push({words[i], current.count + 1});
                visit[i] = true;
            }
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    if(count(words.begin(), words.end(), target) == 0) return 0;
    bfs(begin, target, words);
    
    return result;
}

일단 queue에 뭘 저장할지 생각해봅시다. 필요한 정보는 현재의 문자열과, 몇번 변환을 시도했는지 입니다. State라는 구조체를 만들어서 str, count라는 변수를 각각 선언해줍니다.

 

canJump는 말그대로 a->b로 변환이 가능한지를 판별하는 함수입니다. 변환이 가능하다는것은 두 문자열의 동일 index간 서로 문자가 다른 Index가 하나밖에 없는 경우입니다. 그걸 확인해주면 됩니다.

 

bfs 함수는 내부는 간단합니다.

queue가 바닥날때까지 while문을 돌면서 다른 문자들을 탐색합니다. 탐색시 적합한 다음 원소를 확인하는 방법은 canJump로 진행해주면 됩니다. while문을 돌면서 current.str == target이라면 current.count의 크기를 비교해서 최소값이라면 result를 업데이트해줍니다.

 

words에 target이 없으면 아무리 돌아도 정답이 없습니다. 이런 경우에는 bfs를 돌지않고 바로 리턴할수 있도록 count()함수를 통해 words 내부에 target이 있는지 확인해줍니다. (#include <algorithm> 필요)