프로그래머스 단어변환 c++ dfs ,백트래킹 // dfs 조건있는경우 해결방법

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

프로그래머스

1. dfs 조건있는경우 해결방법

check함수를 만들고

if(check) continue 하면된다!

 

2. 삽질과정

단어길이가 3고정인줄알고  check-> if(count==2) return 1 ; 하드코딩했다가 맞왜틀? 하였다...

 

 

3. 전체코드

#include <bits/stdc++.h>

using namespace std;

int visited[54];
int n,answer, is_possible,word_size;

bool check(string s1, string s2){
    int count=0;
    for(int i=0;i<word_size;++i){
        if(s1[i]==s2[i]) count++;
    }
    
    if(count==word_size-1) return true;
    return false;
}

void dfs(string& now, string& target, vector<string> &words, int depth){

    //cout<<now<<"\n";
    if(depth>words.size()) return;
    
    if(now==target){
        answer=min(answer,depth);
        is_possible=1;
        //cout<<depth<<" 끝\n";
        return;
    }
    
    for(int i=0;i<words.size();++i){
        if(visited[i]) continue;
        if(!check(now,words[i])) continue;
        
        visited[i]=1;
        dfs(words[i],target,words,depth+1);
        visited[i]=0;       
      // dfs 재귀 호출하여 종료되어 여기로 돌아오면, 백트래킹 (방문 표시 해제) 하여 다음분기점부터 다시 탐색을 시작한다.

    }
    
    return;
}

int solution(string begin, string target, vector<string> words) {

    answer=987654321;
    n=words.size();
    word_size=words[0].size();
    dfs(begin,target,words,0);
    
    //cout<<check("log","cog");
    if(!is_possible) return 0;
    return answer;
}