단어변환 C++(dfs/bfs)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

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

코딩테스트 연습 - 단어 변환 | 프로그래머스

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

---

1. 문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

 

문제!!

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

각 단어는 알파벳 소문자로만 이루어져 있습니다. 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다. words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다. begin과 target은 같지 않습니다. 변환할 수 없는 경우에는 0를 return 합니다.

예시

begin	target	words	return
"hit"	"cog"	{ "hot", "dot", "dog", "lot", "log", "cog" }	4
"hit"	"cog"	{ "hot", "dot", "dog", "lot", "log" }	0
"hot"	"lot"	{ "dot", "dog", "lot", "log"}	1
"hit"	"wow"	{ "hot", "dot", "dog", "lot", "log", "cog", "wow" }	0

 

---

2. 문제풀이

어떻게 풀지 고민을 한참했다가 일단시작하자! 하고 시작했는데 막상 푸니까 금방풀었던 문제입니다. 하나씩 접근해보겠습니다.   일단 단어의 개수가 50개가 최대이므로 50개만 넘게 answer를 먼저 잡아둡니다. dfs함수에 시작단어와 타겟단어, 단어리스트, 단어사용여부, 함수의 깊이를 같이 보냅니다. 모든 단어를 현재단어와 비교하면서 1글자가 다른 단어들만 찾습니다.   찾은 단어들을 사용했다고 설정(false->true)하고 시작단어로 변경한뒤 재귀(recursion)시킵니다. 만약 글자차이가 1글자 차이인데 target단어와 똑같다면 answer와 비교해서 작은걸로 바꿔줍니다. 재귀함수를 나올때는 다음에 다시사용해야 하므로 사용했다고 표시했던 부분을 해제(true -> false)합니다. false와 true가 바뀌어도 상관없습니다. 확인만 할수있으면 됩니다.   모든단어와 비교가 끝났다면 answer는 target까지 접근하기위해 최소한의 값을 가지고 있을것입니다. 만약 처음설정한 answer값이 그대로 온다면 일치하는 단어가 없으므로 0을 리턴합니다.

 

---

3. 소스코드

3.1 주석없는 코드

#include <string>
#include <vector>
using namespace std;
int answer{ 100 };
 
void dfs(string begin, string target, vector<string> words, vector<bool>& useCheck, int cnt = 0) {
    for (int i = 0; i < words.size(); i++) {
        int count{ 0 };
        for (int j = 0; j < words[i].length(); j++)
            if (!useCheck[i] && begin[j] != words[i][j])    count++;
        if (count == 1) {
            if (target == words[i] && answer > cnt + 1) {
                answer = cnt + 1;
                return;
            }
            useCheck[i] = true;
            dfs(words[i], target, words, useCheck, cnt + 1);
            useCheck[i] = false;
        }
    }
}
 
int solution(string begin, string target, vector<string> words) {
    vector<bool> useCheck(words.size(), false);
    dfs(begin, target, words, useCheck);
    if (answer == 100)   return 0;
    return answer;
}

3.2 주석있는 코드

#include <string>
#include <vector>
using namespace std;
int answer{ 100 };
//시작단어, 목표단어, 단어리스트, 단어리스트사용여부, 목표까지 들어간 횟수(깊이)
void dfs(string begin, string target, vector<string> words, vector<bool>& useCheck, int cnt = 0) {
    //단어의 사이즈만큼 반복
    for (int i = 0; i < words.size(); i++) {
        //알파벳끼리 일치여부 초기화
        int count{ 0 };
        //한글자씩 비교하면서 글자가 다를경우 카운트 증가
        for (int j = 0; j < words[i].length(); j++)
            if (!useCheck[i] && begin[j] != words[i][j])    count++;
        //카운트가 1이라면(한 글자만 다른경우)
        if (count == 1) {
            //1글자만 다른 단어가 target단어이고 answer가 지금까지 들어온 깊이+1보다 큰경우 answer변경
            if (target == words[i] && answer > cnt + 1) {
                answer = cnt + 1;
                return;
            }
            //단어를 사용했다 체크하고 재귀
            useCheck[i] = true;
            dfs(words[i], target, words, useCheck, cnt + 1);
            //함수를 나온경우 단어사용여부 해제
            useCheck[i] = false;
        }
    }
}
 
int solution(string begin, string target, vector<string> words) {
    //사용한 단어 체크용(words의 길이만큼 생성하고 fasle로 초기화한다.)
    vector<bool> useCheck(words.size(), false);
    dfs(begin, target, words, useCheck);
    //answer가 100이면 target까지 갈수없으므로 0을 리턴한다.
    if (answer == 100)   return 0;
    //위조건이 무시된다면 target까지 제일짧은 횟수를 리턴
    return answer;
}

3.3 테스트 코드 추가

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int answer{ 100 };
//시작단어, 목표단어, 단어리스트, 단어리스트사용여부, 목표까지 들어간 횟수(깊이)
void dfs(string begin, string target, vector<string> words, vector<bool>& useCheck, int cnt = 0) {
    //단어의 사이즈만큼 반복
    for (int i = 0; i < words.size(); i++) {
        //알파벳끼리 일치여부 초기화
        int count{ 0 };
        //한글자씩 비교하면서 글자가 다를경우 카운트 증가
        for (int j = 0; j < words[i].length(); j++)
            if (!useCheck[i] && begin[j] != words[i][j])    count++;
        //카운트가 1이라면(한 글자만 다른경우)
        if (count == 1) {
            //1글자만 다른 단어가 target단어이고 answer가 지금까지 들어온 깊이+1보다 큰경우 answer변경
            if (target == words[i] && answer > cnt + 1) {
                answer = cnt + 1;
                return;
            }
            //단어를 사용했다 체크하고 재귀
            useCheck[i] = true;
            dfs(words[i], target, words, useCheck, cnt + 1);
            //함수를 나온경우 단어사용여부 해제
            useCheck[i] = false;
        }
    }
}
 
int solution(string begin, string target, vector<string> words) {
    //사용한 단어 체크용(words의 길이만큼 생성하고 fasle로 초기화한다.)
    vector<bool> useCheck(words.size(), false);
    dfs(begin, target, words, useCheck);
    //answer가 100이면 target까지 갈수없으므로 0을 리턴한다.
    if (answer == 100)   return 0;
    //위조건이 무시된다면 target까지 제일짧은 횟수를 리턴
    return answer;
}
 
void print(string begin, string target, vector<string> words, int answer) {
    ::answer = 100;
    int t = solution(begin, target, words);
    cout << t << " , ";
    if (t == answer)        cout << "정답" << endl;
    else        cout << "틀림" << endl;
}
 
int main() {
    print("hit", "cog", { "hot", "dot", "dog", "lot", "log", "cog" }, 4);
    print("hit", "cog", { "hot", "dot", "dog", "lot", "log" }, 0);
    print("hot", "lot", { "dot", "dog", "lot", "log" }, 1);
    print("hit", "wow", { "hot", "dot", "dog", "lot", "log", "cog", "wow" }, 0);
    return 0;
}

---

4. 결과