알고리즘(C++) / 프로그래머스 level 3 : 단어 변환

level 3 : 단어 변환

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

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

 

코드

//프로그래머스 단어 변환
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <map>

using namespace std;

vector<string> words_copy;

//알파벳 하나만 다를때: true, else: false
bool compare(string a, string b) {
    int check = 0;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i])
            check++;
    } //단어 a, b 비교
    if (check == 1)
        return true;
    return false;
}

int BFS(string begin, string target) {
    queue <pair<string, int>> q;
    q.emplace(begin, 0);

    map<string, int> visited;
    visited[begin]++;


    while (!q.empty()) {
        if (q.front().first == target) {
            return q.front().second;
        }//find target
        for (int i = 0; i < words_copy.size(); i++) {
            if (visited[words_copy[i]] == 0) { //방문하지 않은 단어
                if (compare(q.front().first, words_copy[i]) == true) { //단어 변환 가능할 때
                    q.emplace(words_copy[i], q.front().second + 1);//queue push
                    visited[words_copy[i]]++; //방문
                }
            }
        }
        q.pop();
    }

    return 0;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    words_copy = words; //copy 전역변수 변경

    answer = BFS(begin, target);

    return answer;
}

int main() {
    string begin = "hit";
    string target = "cog";
    vector<string> words = { "hot", "dot", "dog", "lot", "log", "cog" };
    cout << solution(begin, target, words);
    return 0;
}

 

설명

이번 문제는 '최소'의 단계를 거쳐 target을 찾는것이다. 최소한으로 찾아야 하므로 BFS로 구현하였다.

BFS는 최단 경로를 찾기에 효과적이다. 

queue에 단어와 변환 횟수를 쌍으로 push해준다. 

queue에서 가장 앞 단어와 방문하지 않은 다른 단어 중 변환이 가능한 단어를 찾아 다음 queue에 넣어주고 vistied를 증가시켜준다.(이미 방문한 단어는 또 방문하지 않는다. map을 이용)

단어가 target과 같다면 몇 단계를 거쳤는지 return할 수 있다. 

변환할 수 없는 경우에는 0을 return 한다.

 

고찰

구글링으로 다른 사람의 풀이를 봤다. DFS로 푼사람이 많았다. '최소'나 '최단' 이라는 말이 있다면 내 생각엔 DFS보다 BFS로 푸는 것이 더 효율적인거 같다.