[프로그래머스 DFS/BFS] 단어변환 - C++

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/43163

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

 

dfs로 풀었습니다.

재귀함수, dfs 기본 구현에 충실한 문제였습니다. 

dfs, bfs에 대해서는 추후에 포스팅을 할 예정입니다.

 

[주석 없는 코드]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int ans = 50;
bool check[50];

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

void dfs(string begin, string target,vector<string>words,int cnt){
    if(begin==target){
        ans = min(ans,cnt);
        return;
    }
    for(int i=0; i<words.size();i++){
        if(diff(begin,words[i]) && !check[i]){
            check[i]=true;
            dfs(words[i],target,words,cnt+1);
            check[i]=false;
        }
    }
    return;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    dfs(begin,target,words,0);
    answer = ans;
    if(answer == 50)
        return 0;
    return answer;
}

 

[주석 있는 코드]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int ans = 50;
bool check[50];

//다른 문자가 1개인지 확인하는 함수
bool diff(string a, string b){
    int dif =0;
    for(int i=0; i<a.size();i++){
        if(a[i]!=b[i])
            dif++;//다른 글자 수
        if(dif >1)
            break;
    }
    if(dif==1)
        return true;
    else
        return false;
}

void dfs(string begin, string target,vector<string>words,int cnt){
	if(answer <= cnt)//이미 깊이(cnt)가 이전에 찾은 answer보다 크면 탐색할 필요가 없습니다. 
    	return;
    if(begin==target){
        ans = min(ans,cnt);
        return;
    }
    for(int i=0; i<words.size();i++){
        //문자열이 하나만 다르면서 동시에 방문 안한 단어이면 탐색
        if(diff(begin,words[i]) && !check[i]){
            check[i]=true;
            dfs(words[i],target,words,cnt+1);
            check[i]=false;
        }
    }
    return;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    dfs(begin,target,words,0);
    answer = ans;
    if(answer == 50)//target문자열을 만나지 못했을 때
        return 0;
    return answer;
}