DFS/BFS 단어변환

<문제>

 

 

 

<문제 풀이>

생각의 흐름 :

1.아이거.. DFS, BFS문제니까, DFS,BFS사용해서 푸는 문제인가보다. (근데 실전에서는 이게 무슨 유형의 문제인지 당연히 모를테니까 눈으로 많이 익혀두자)

 

2.뭔가.. DFS로 풀 수 있을 것 같다는 생각이 들었다.. 왜? words에 속해있는 단어들을 한번씩 다 돌아다니면서(재귀) begin이 조건에 따라 바뀌고, begin과 target과 같아졌을 때 재귀가 끝나는 형식으로 구현하면 되겠다! 

 

3.그렇다면 begin이 words에 있는 단어로 바뀌는 조건은 무엇인가? 

1. beign의 단어가 words의 단어와 비교했을 때 철자가 하나만 다를 때(이외에 철자는 모두 같을 때),
2. 한번도 접근하지 않은 단어일 때 (visited[] 이용 - 중복 방지. 무한 재귀 방지)
3. + 몇 번이나 begin이 바뀌었는지 (target과 같아질 때 까지) 세는 count변수

4.begin target과 같아질 때는 그동안 count로 센 수를 min함수에 삼항 연산자로 대입( min = min > count ? count : min)하여 최소의 수를 찾는다. 

 

5.따라서 3을 이행할 수 있는 조건문, 3-1을 수행할 수 있는 함수 정도를 만들면 dfs 재귀를 이용한 방법으로 풀 수 있을 것 같다는 생각이 들었다.

 

 

<코드 구현>

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int Min = 9999;

bool compareString(string a, string b) {
    int count=0;
    for(int i=0; i<a.size(); ++i){
        if(a[i] != b[i]) count++;
        if(count > 1) return false;
    }
    
    if(!count) return false;
    return true;
}

void dfs(string begin, string target, vector<string> words, int count, vector<bool> visited) {        
   
    if(begin == target) {
        Min = Min > count ? count : Min;
        return;
    }
    
    for(int i=0; i<words.size(); ++i) {
        if(!compareString(begin, words[i]) || visited[i]) continue;
        string tmp;
        tmp = begin;
        begin = words[i];
        count++;
        visited[i] = true;
        dfs(begin, target, words, count, visited);
        visited[i] = false;
        count--;
        begin=tmp;
    }
    
    return;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    vector<bool> visited(50,false);
    dfs(begin, target, words, 0, visited);
    
    if(Min!=9999) answer = Min;
    else answer =0;
        
    
    
    return answer;
}