[프로그래머스 Level_3 / C++] 단어 변환

dfs 문제이다. 

 

#접근방법 

1. 현재 들고있는 문자열과 words 배열의 문자열들을 하나하나 비교한다. 
2. 현재 들고 있는 문자열과 words 배열의 특정 문자열과 비교했을 때 딱 하나만 다를 경우 dfs를 호출한다. 
3. 이때 dfs를 호출하기 전에 문자열의 인덱스 번호를 방문처리를 해주고 dfs 호출이 끝난 후 방문처리를 풀어준다.

#include <string>
#include <vector>
#include <algorithm> 
#include <iostream>
int v[50]; 
using namespace std;
vector <string> w; 
string t; 
int result = 987654321; 
void dfs(string s,  int cnt ){
    if(s==t){
        result = min(result, cnt);
        return; 
    }         
    for(int i=0; i<w.size(); i++){
        if(v[i])continue;
        int check =0;  
        for(int j =0; j<s.size(); j++){
            if(s[j]==w[i][j])check++;             
        }
        if(check==s.size()-1){        
            v[i]=1;           
            dfs(w[i], cnt+1);            
            v[i]=0; 
        }
    }    
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    w = words; 
    t = target; 
    dfs(begin, 0); 
    if(result==987654321)return 0; 
    else return result;
}

 

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