[프로그래머스, C++] 단어 변환

문제 링크

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

 

 

 

풀이

재귀 DFS로 풀었다.

 

// check_1_diff()

- 문자가 하나만 다를 경우, true

 

// dfs()

0. 탈출조건

만약, target의 문자열로 바뀌었을 경우는 들어간 깊이?(count)로 return 시켰다.

그리고 만약, string형의 visit 변수의 '0'이 없다면 모두 방문했다는 소리다.

따라서, 변환할 수 있을 때의 (최대 깊이+1 = 51)로 리턴시킨다.

1. init

깊이를 51(변환할 수 있을 때의 최대 깊이+1)로 초기화

 

2. process

반복문 --- words의 개수만큼

{

    해당 인덱스가 이미 방문했거나, 문자가 1개만 다른 경우가 아니라면 continue

    방문한다고 체크

    dfs 호출(해당 인덱스의 word로)

    방문 해제 --- 다음 원소가 방문할 수 있도록

    호출된 dfs의 깊이 반환값과 최솟값을 비교하여 갱신

}

깊이를 리턴

 

// solution

1. init

방문 검사 string을 '0'으로 초기화

 

2. process

dfs 호출된 깊이 반환값을 answer에 할당

만약, 51일 경우 못찾은 경우므로 answer에 0을 할당

return answer;

 

 

#include <string>
#include <vector>

using namespace std;

// 한 번에 한 개의 알파벳만 바꿀 수 있다
// words에 있는 단어로만 변환 가능

// 처음 시작 문자열 begin
// 원하는 문자열 target
// 단어 집합 words

bool check_1_diff(string s1, string s2){
    int count = 0;      // 문자 다른 갯수
    for(int i=0; i<s1.size(); i++){
        if(s1[i] != s2[i]) count++;
    }
    if(count != 1) return false;
    return true;        // 1개만 다를 경우 true
}

int dfs(string begin, string target, vector<string> words, string visit, int count){
    if(begin == target) return count;       // target이 됨
    if(visit.find('0') == string::npos) return 51;       // 모든 방문 완료
    
    // init
    int ret = 51;     // 최대값
    
    // process
    for(int i=0; i<words.size(); i++){
        if(visit[i]=='1' || !check_1_diff(begin, words[i])) continue;
        visit[i]='1';       // 방문 체크
        int cnt = dfs(words[i], target, words, visit, count+1);     // dfs
        visit[i]='0';       // 다른 인덱스를 위해 방법 체크 풀기
        ret = min(ret, cnt);        // 변환 횟수 최소값 갱신
    }
    return ret;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    // init
    string visit(words.size(), '0');        // 방문 검사
    
    // process
    answer = dfs(begin, target, words, visit, 0);       // dfs
    if(answer==51) return 0;        // 못찾음
    return answer;      // 변환 단계 최솟값 리턴, 변환할 수 없는 경우 0 리턴
}