[Programmers] 깊이/너비 우선 탐색(DFS/BFS) > 단어 변환(c++)

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

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

*begin = "hit" 에서부터 target= "cog" 까지 DFS횟수(=cnt)를 모두 result에 저장해서 그 중 최솟값을 구하는 방법으로 풀었다.

 

1. words벡터 집합 중 target과 같은것이 없으면 Return 0

2. target과 같은 원소가 하나라도 있으면 DFS 실행

3. begin과 words[k]의 문자 차이를 diff변수에 저장하고, 1개만 틀린 words[k]에 한에서만 DFS실행

4. DFS를 실행하기 전 isVisited[k] = true로 방문 표시를 해두고, begin을 words[k] 업데이트 후 DFS를 실행한다.

5.  3~4를 반복하며 begin과 target이 같아질때만 result벡터에 cnt를 push한다.

6. k가 words.size()를 넘을때까지 begin과 target이 일치하지 않으면 DFS를 빠져나오고, isVisited[k] = false 다시 미방문 상태로 바꾼다. ( 다른 DFS에서 출발할때, 다시 재사용해야 하기 때문)

7. 모든 DFS가 끝나고, result에 저장되어있는 cnt 중 중 최솟값을 answer에 저장한다.

 

*DFS에서 cnt는 DFS가 실행되는 횟수로, 그림 기준으로 노드 사이 가지 개수에 해당한다.

 

 

 

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define SIZE 50

int answer = 0;
int isVisited[SIZE];
vector<int> result; //모든 결과 저장

void DFS(string begin, string target, vector<string> words, int cnt){
    
    if(begin == target) {result.push_back(cnt); return; }
    for(int k=0;k<words.size();k++){
        int diff = 0;
        for(int i=0;i<begin.size();i++) if(!isVisited[k] &&(begin[i] != words[k][i])) diff++;
        
        if(diff==1) {
            isVisited[k] = true;
            DFS(words[k], target, words, cnt+1);
            isVisited[k] = false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    vector<string>::iterator it;
    it = find(words.begin(), words.end(), target);
    if(it == words.end()) return 0; //words안에 target이 없을 경우(변환할 수 없는 경우)
    
    DFS(begin, target, words, 0);
    answer = *min_element(result.begin(), result.end()); //최솟값 저장
    return answer;
}

 

 

 

main포함 코드

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define SIZE 50

int answer = 0;
int isVisited[SIZE];
vector<int> result; //모든 결과 저장

void DFS(string begin, string target, vector<string> words, int cnt){
    
    if(begin == target) {result.push_back(cnt); return; }
    for(int k=0;k<words.size();k++){
        int diff = 0;
        for(int i=0;i<begin.size();i++) if(!isVisited[k] &&(begin[i] != words[k][i])) diff++;
        
        if(diff==1) {
            isVisited[k] = true;
            DFS(words[k], target, words, cnt+1);
            isVisited[k] = false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    vector<string>::iterator it;
    it = find(words.begin(), words.end(), target);
    if(it == words.end()) return 0; //words안에 target이 없을 경우(변환할 수 없는 경우)
    
    DFS(begin, target, words, 0);
    answer = *min_element(result.begin(), result.end()); //최솟값 저장
    return answer;
}

int main(int argc, const char *argv[])
{
    string begin = "hit";
    string target = "cog";
    vector<string> words={"hot", "dot", "dog", "lot", "log", "cog"};
    
    cout << solution(begin, target, words);
    
    return 0;
}