[C++][Programmers][DFS/BFS] 단어 변환

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

프로그래머스

 

[해결책]

단어가 1개 차이나는 단어를 찾아서 BFS를 계속 돌린다.

이때 탐색 count를 계속 체크해가며 최소 count값을 구해야 한다.

종료조건은 탐색 단어를 찾았을 때와 words배열 끝에 도달했음에도 target단어를 못만났을 경우다.

 

[알아둘 것]

1) INT_MAX는 limits.h를 선언해줘야 한다.

2) 재탐색을 위해 방문체크 했다가 풀어주는 부분.

 

[코드]

#include <string>
#include <vector>
#include <iostream>
#include <limits.h>
using namespace std;

int answer = INT_MAX;

int DFS(string begin, string target, vector<string> words, vector<bool> &isVisited, int searchCount){

    //searchCount가 answer보다 크면 탐색 필요 없음
    if(searchCount > answer) return answer;
    
    //탐색하는 단어가 target이랑 같으면 answer 값 업데이트하고 return
    if(begin == target){
        answer = searchCount;
        cout << answer << " ";
        return answer;
    }

    //단어개수만큼 반복하며 단어 하나씩 선택
    //방문한적 없는 단어선택 
    for(int i = 0; i < words.size(); i++){
        if(isVisited[i]) continue;

        //단어 1개 차이나는지 체크
        int diffCount = 0;
        for(int j = 0; j < words[i].length(); j++){
            if(begin[j] != words[i][j]) diffCount++;            
        }
        
        if(diffCount == 1){
            cout << words[i] << " ";
            //방문체크   
            isVisited[i] = true;
            DFS(words[i], target, words, isVisited, searchCount+1);
            //재방문을 위해 방문체크 해제
            isVisited[i] = false;
        }
    } 
    return answer;
}

int solution(string begin, string target, vector<string> words) {
    vector<bool> isVisited(words.size(), false);
    answer = DFS(begin, target, words, isVisited, 0);
    return (answer == INT_MAX) ? 0 : answer; 
}