[DFS, 난이도 중] 프로그래머즈, 단어 변환

begin을 시작점으로 두고 words중에서 현재 단어와 알파벳 하나만 차이나는 단어로 변환해 나가며, 최소 몇 번째 변환만에 target이 되는가 계산하는 문제이다.

target이 될 때 까지 연속으로 변환한다는 점에서 DFS문제라는 것을 알았다.

 

문자열 a,b가 알파벳 하나만 차이나는가 여부를 판단하기 위해 connect 함수를 만들었다.

먼저 connect 함수를 이용하여 begin과 words를 비교해나가며 참일 경우 간선을 설정한다.

다음에는 words단어끼리 간선을 설정한다.

그리고 편리를 위해 정점마다 번호를 매겨주었다.

target은 정점 번호를 0으로 정했고, words의 i번째 단어의 정점 번호를 i+1로 매겼다.

words에서 target이 있는 위치를 알기 위해 target_index 변수도 만들었다. 

 

몇 번째 변환만에 target이 되는지 판단하기 위해 dfs의 매개변수에 depth도 넣어주고, target이 되었을 경우 depth의 최솟값을 갱신해주기 위해 min함수를 이용했다.

 

테스트 케이스 5개 모두 통과

 

#include <string>
#include <vector>
using namespace std;
vector<int> a[51];
bool visited[51];
int target_index;
int answer=52;

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

void dfs(int x,int depth){
    if(x==target_index){
        answer = min(answer,depth);
        return;
    }
    for(int i=0;i<a[x].size();i++){
        int y = a[x][i];
        if(!visited[y]){
            visited[y]=true;
            dfs(y,depth+1);
            visited[y]=false;
        }
    }
    return;
}

int solution(string begin, string target, vector<string> words) {
    for(int i=0;i<words.size();i++){
        if(target==words[i]) target_index=i+1; //target과 일치하는 words의 인덱스
        if(connect(begin,words[i])) a[0].push_back(i+1); //시작점의 간선설정
        for(int j=0;j<words.size();j++){ //words간의 간선설정
            if(connect(words[i],words[j])) a[i+1].push_back(j+1);
        }
    }
    dfs(0,0);
    return answer;
}