고득점 kit의 단어변환 문제를 BFS를 활용해서 풀어보자. 🔥

문제

해당 문제는 프로그래머스 고득점 kit의 단어변환 문제입니다.
문제는 여기 클릭해서 확인해주세요! (문제 저작권 보호차원 링크로 공유드립니다😟)

궁금한점 댓글로 남겨주시면 성실히 답변하겠습니다👍
+ 감상평 댓글로 남겨주시면 힘이됩니다. 🙇

풀이

해당 문제는 시작점을 기준으로 한 글자 단어를 계속 바꿔가며 타겟을 찾는 문제이다.

전형적 완전 탐색 문제이다. 완전 탐색을 푸는 방법은 여러가지가 있지만, 그 중 대중적으로 사용되는 방법은 dfs / bfs 방법이다. 해당 문제는 두 가지 방법으로 다 풀 수 있고, 본인은 dfs 방법 으로 문제를 해결했다.

문제 접근 과정

아래의 그림과 같이, input 값들을 하나의 노드로 정의하고, begin 부터 한 글자만 변경해 동일할 경우 해당 노드로 옮겨간다. 이후 현재 노드가 target값과 동일한지 판단하는 방법으로 풀었다.

chagne_words

간단하게 위의 그림을 이해해보자.

Case 1.

Case 2.

Case3.

소스코드

#include <string>
#include <vector>

using namespace std;

static int answer = 50;

void dfs(string begin, const string target, vector<bool>& check, const vector<string>& words, int count = 0) {

    if (begin == target) {
        if (answer > count) answer = count;
        return;
    }

    for (int i = 0; i < words.size(); i++) {
        int b_cnt = 0;
        if (check[i]) continue;

        for (int j = 0; j < words[i].length(); j++) {
            if (begin[j] != words[i][j]) b_cnt++;
        }

        if (b_cnt == 1) {
            check[i] = true;
            dfs(words[i], target, check, words, count + 1);
            check[i] = false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    vector<bool> check(words.size(),false);

    dfs(begin, target, check, words);
    return answer == 50 ? 0 : answer;
}

해당 문제의 dfs의 핵심은 탈출조건 과 방문 유무를 검사하는 visisted 배열이다.

탈출조건

방문 유무 검사

Appendix

해당 소스코드는 필요한 부분에 주석을 추가한 소스코드이다. 해당 부분은 참고용으로 보기 바란다.

/***********************

해당 문제 조건
- 각 단어는 알파벳 소문자
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같음
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어 (최대 50)
- begin과 target은 같지 않음
- 변환할 수 없는 경우에는 0를 return

***********************/

#include <string>
#include <vector>

using namespace std;

static int answer = 50;

void dfs(string begin, const string target, vector<bool>& check, const vector<string>& words, int count = 0) {

    /* 탈출 조건 : begin == target */
    if (begin == target) {
        if (answer > count) answer = count;
        return;
    }

    for (int i = 0; i < words.size(); i++) {
        int b_cnt = 0;

        /* 애당초 검사했던 words라면 단어 같은지 알 필요도 없음. */
        if (check[i]) continue;

        for (int j = 0; j < words[i].length(); j++) {
            /* 글자 다른 횟수 세기 */
            if (begin[j] != words[i][j]) b_cnt++;
        }

        /*
          글자 하나만 다른 경우
            해당 글자로 begin point를 변경하고 bfs 돌면됨.
            중복 되는 경우가 없기 때문에 < 2가 아닌 == 1 로 확인하면 됨.
        */
        if (b_cnt == 1) {
            check[i] = true;
            dfs(words[i], target, check, words, count + 1);
            check[i] = false;
        }
    }
}

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

배운 점