Coding Test] 단어 변환 문제(DFS)

[Programmers School 문제 링크]

• Code

#include <string>
#include <vector>

using namespace std;

int answer; //solution에서 words.size()+1로 초기화

void DFS(string cur_string, string target, vector<string> words, int depth, bool* visit)
{
    //words를 모두 확인 || 변환 성공
    if(depth > words.size() || cur_string == target)
    {
        //answer는 words.size()+1이므로 depth보다 작거나 같을 수 밖에 없음
        answer = answer > depth ? depth : answer;
        return;
    }

    //변환 중인 현재 단어에서 변환 가능한 단어의 index vector
    vector<int> next;
    //words 순회
    for(int word = 0; word < words.size(); word++)
    {
        //이미 변환에 쓰인 단어는 스킵
        if(visit[word])
            continue;

        //같은 글자 수
        int matchCount = 0;
        for(int i = 0; i < cur_string.length(); i++)
        {
            //한글자씩 비교 후 같을 때마다 matchCount + 1
            if(cur_string[i] == words[word][i])
                matchCount++;

            //같은 글자 수가 단어의 길이 -1과 같으면 변환 가능
            if(matchCount == cur_string.length()-1)
                next.push_back(word);
        }
    }

    //변환 가능한 Index 순회
    for(int i = 0; i < next.size(); i++)
    {
        visit[next[i]] = true;                                  //방문할 Index 저장
        DFS(words[next[i]], target, words, depth + 1, visit);   //단어 변환
        visit[next[i]] = false;                                 //방문했었던 Index 삭제
    }
}

int solution(string begin, string target, vector<string> words) {
    answer = words.size() + 1;
    for(int word = 0; word < words.size(); word++)
    {
        if(target == words[word])
        {
            bool* visit = new bool[words.size()];
            for(int i = 0; i <  words.size(); i++)
                visit[i] = false;

            DFS(begin, target, words, 0, visit);
            break;
        }
    }
    return answer > words.size() ? 0 : answer;
}

---

• DFS

/*
cur_string    : 현재 string
target        : 목표 string
words         : 단어 모음
depth         : 변환 횟수
visit         : 변환한 단어 체크
*/
void DFS(string cur_string, string target, vector<string> words, int depth, bool* visit)
{
    //words 끝 || 목표로의 변환 성공
    if(depth > words.size() || cur_string == target)
    {
        //answer는 words.size()+1이므로 depth보다 작거나 같을 수 밖에 없음
        answer = answer > depth ? depth : answer;
        return;
    }

    //변환 중인 현재 단어에서 변환 가능한 단어의 index vector
    vector<int> next;
    //words 순회
    for(int word = 0; word < words.size(); word++)
    {
        //이미 변환에 쓰인 단어는 스킵
        if(visit[word])
            continue;

        //같은 글자 수
        int matchCount = 0;
        for(int i = 0; i < cur_string.length(); i++)
        {
            //한글자씩 비교 후 같을 때마다 matchCount + 1
            if(cur_string[i] == words[word][i])
                matchCount++;

            //같은 글자 수가 단어의 길이 -1과 같으면 변환 가능
            if(matchCount == cur_string.length()-1)
                next.push_back(word);
        }
    }

    //변환 가능한 Index(next) 순회 / DFS
    for(int i = 0; i < next.size(); i++)
    {
        visit[next[i]] = true;                                  //방문할 Index 저장
        DFS(words[next[i]], target, words, depth + 1, visit);   //단어 변환(DFS)
        visit[next[i]] = false;                                 //방문했었던 Index 삭제
    }
}