프로그래머스 - 단어 변환

DFS를 이용하여 풀었는데, 사실 처음에 생각했던 BFS를 이용해서도 풀 수 있는 것 같다. 

 

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int visit[51];
int res = 987654321;
int check(string a, string b)
{
    int cnt = 0;
    for(int i=0; i<a.size(); i++)
    {
        if (a[i] != b[i])
            cnt++;
    }
    return cnt;
}
 
void dfs(string begin, string target, vector<string> words, int cnt, int visit[51])
{
    if (cnt > words.size())
        return ;
    if (begin == target)
    {
        res = min(res, cnt);
        return;
    }
    for(int i=0; i<words.size(); i++)
    {
        if (check(begin, words[i]) == 1 && !visit[i])
        {
            visit[i] = 1;
            int tmp_visit[51];
            for(int j=0; j<words.size(); j++)
                tmp_visit[j] = visit[j];
            dfs(words[i], target, words, cnt + 1, tmp_visit);
        }
    }
}
 
int solution(string begin, string target, vector<string> words) {
    dfs(begin, target, words, 0, visit);
    if (res == 987654321)
        return (0);
    return res;
}

백준 문제에서 visit배열과 map배열을 복사해서 넘겼었는데, 이 경우에도 visit 배열을 복사해서 재귀를 호출해줌으로써 모든 경우에 대해서 탐색할 수 있게 된다. 

 

BFS로 푼 코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int res = 987654321;
int visit[50];
int check(string a, string b)
{
    int cnt = 0;
    for(int i=0; i<a.size(); i++)
    {
        if (a[i] != b[i])
            cnt++;
    }
    return cnt;
}
 
int solution(string begin, string target, vector<string> words) {
    queue<pair<string, int> > q;
    q.push(make_pair(begin, 0));
    int res = 987654321;
    while (!q.empty())
    {
        pair<string, int> cur = q.front();
        q.pop();
        if (cur.first == target)
        {
            res = min(res, cur.second);
            break;
        }
        for(int i=0; i<words.size(); i++)
        {
            if (check(cur.first, words[i]) == 1 && !visit[i])
            {
                visit[i] = 1;
                q.push(make_pair(words[i], cur.second + 1));
            }
        }
    }
    if (res == 987654321)
        return (0);
    return res;
}