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

▶문제설명

코딩테스트 연습 > DFS/BFS > 단어 변환

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

▶ 설계

---

DFS 탐색으로 문제를 해결해보자.

한 번에 한 개의 알파벳만 바꾸어서 word에 있는 단어 중 하나로 변환할 수 있는지 모든 경우를 탐색해보면 되는 문제이다.

복잡한 것 없이 문제에서 요구하는데로 재귀 함수만 잘 구현하면 간단히 해결될 것으로 보인다.

▶ 구현

---

우선 재귀함수의 매개변수와 리턴타입을 정해보자.

int findWord(string nowWord, const string& targetWord, const vector<string>& words, int cnt){
    int answer = 987654321;
 
    return answer;
}

cnt변수는 재귀 함수의 깊이를 나타내는 변수이다.

정답을 찾아가는 경로 중 최소값을 찾아야 하므로 answer를 987654321이라는 값으로 초기화해주었다.

answer를 리턴하기 전에 answer에는 최소 값이 들어있게 되거나 targetWord로 갈 수 있는 방법이 없을 경우엔 987654321이 그대로 들어있게 될 것이다.

재귀 함수의 종료 조건식을 세워주자.

int findWord(string nowWord, const string& targetWord, const vector<string>& words, int cnt){
    int answer = 987654321;
 
    if(nowWord.compare(targetWord) == 0){
        return cnt;
    }
    
    return answer;
}

nowWord가 targetWord와 같아졌을 때 재귀 함수의 깊이를 반환하도록 구현했다.

이제 핵심이라고 할 수 있는 가능한 모든 경우를 탐색하며 재귀 호출하는 부분을 구현해야한다.

int findWord(string nowWord, const string& targetWord, const vector<string>& words, int cnt){
    int answer = 987654321;
    if(nowWord.compare(targetWord) == 0){
        return cnt;
    }
    
    for(int i=0; i<nowWord.length(); i++){
        if(nowWord[i] == targetWord[i]) 
            continue;
        
        string nextWord(nowWord);
        for(int j=0; j<26 ;j++){
            nextWord[i]='a'+j;
            for(int k=0; k<words.size(); k++){
                if(words[k].compare(nextWord) == 0){
                    int ret = findWord(nextWord, targetWord, words, cnt+1);
                    answer = min(answer,ret);
                }                           
            }
        }
    }
    return answer;
}

nowWord의 인덱스를 순회하면서 targetWord와 같은 인덱스에 있는 알파벳이 동일할 경우에는 다른 알파벳으로 교체해볼 필요가 없으므로 continue문으로 무시하도록 구현했다.

그렇지 않은 경우에는 해당 인덱스의 알파벳을 26개의 알파벳으로 일일이 변경한 뒤 words에서 일치하는 단어가 있는지 확인하고 있다.

일치하는 단어가 있는 경우에는 함수를 재귀적으로 호출하게 되는데, 그 단어를 첫 번째 인자로 넘겨주고 깊이를 나타내는 cnt를 1 증가시켜서 넘겨준다.

첫 번째 인자로 nextWord를 넘겨주든  words[k]를 넘겨주든 똑같은 결과를 얻을 수 있다.

그리고 answer의 값보다 재귀 호출로 반환 받은 값이 더 작은 경우에 answer의 값을 갱신하도록 구현했다.

이렇게 하고 프로그램을 돌리면 무한루프에 빠지게 된다. 그 이유는 조금만 생각해보면 알 수 있다.

이미 선택된 단어를 죽을 때까지 계속해서 선택할 수 있기 때문이다. 이 문제를 해결해보자.

bool usedWord[50];
 
int findWord(string nowWord, const string& targetWord, const vector<string>& words, int cnt){
    int answer = 987654321;
    if(nowWord.compare(targetWord) == 0){
        return cnt;
    }
    
    for(int i=0; i<nowWord.length(); i++){
        if(nowWord[i] == targetWord[i]) 
            continue;
        
        string nextWord(nowWord);
        for(int j=0; j<26 ;j++){
            nextWord[i]='a'+j;
            for(int k=0; k<words.size(); k++){
                if(usedWord[k] == false && words[k].compare(nextWord) == 0){
                    usedWord[k] = true;
                    int ret = findWord(nextWord, targetWord, words, cnt+1);
                    answer = min(answer,ret);
                    usedWord[k] = false;
                }
            }
        }
    }
    return answer;
}

이렇게 조금만 수정해주면 word[k]가 이미 사용된 단어인 경우에는 무시하게 된다.

이런 브루트 포스 문제는 재귀호출을 해준 뒤에 다시 원래의 상태로 돌려주는 부분이 있어야 모든 경우를 탐색할 수 있음에 유의하자.

▶ 결과

---

▶Solution

---

[소스코드 보기]