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

김개발·2021년 8월 19일

cpp level3 알고리즘 프로그래머스

프로그래머스

목록 보기

6/42

문제 푼 날짜 : 2021-08-19

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43163

접근 및 풀이

주어진 단어들은 모두 길이가 같고, 단어의 길이도 10이하로 제한되어있다. 또한 단어의 갯수가 최대 50개라고 주어졌기 때문에 완전 탐색을 진행하려고 했다.
아래의 조건에 맞게 탐색하기 위해 주어진 단어(begin)의 하나의 알파벳을 목표단어(target)의 동일한 위치의 알파벳으로 변경해보면서 단어목록에 존재하는 단어인지 아닌지를 체크하여 재귀함수를 호출하였다.
이렇게 하면 될 것 같았는데, 결과가 segmentation fault가 발생해서 한참을 잘못된 점을 찾다가 결국 다른 분들의 풀이를 참고하였다.

한 번에 한 개의 알파벳만 바꿀 수 있습니다.

words에 있는 단어로만 변환할 수 있습니다.

참고한 풀이 : https://hwan-shell.tistory.com/258

코드(오답)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string Begin, Target;
vector<string> Words;
int answer;

void dfs(string str, int idx, int cnt, int visited) {
    if (visited == (1 << Target.size()) - 1) {
        if (str == Target) {
            answer = min(answer, cnt);
        }
        return;
    }
    
    string s = str;
    s[idx] = Target[idx];
    
    if (find(Words.begin(), Words.end(), s) != Words.end()) {
        dfs(s, (idx + 1) % Target.size(), cnt + 1, visited |= (1 << idx));
        visited &= ~(1 << idx);
    } else {
        dfs(str, (idx + 1) % Target.size(), cnt, visited);
    }
}

int solution(string begin, string target, vector<string> words) {
    answer = 987654321;
    Begin = begin, Target = target, Words = words;
    if (find(words.begin(), words.end(), target) == words.end()) {
        return 0;
    } else {
        for (int i = 0; i < target.length(); i++) {
            string temp = begin;
            dfs(temp, i, 0, 0);
            cout << endl;
        }
    }
    return answer;
}

코드(통과)

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

#define INF 987654321

string Target;
vector<string> Words;
bool checked[51];
int answer;

void dfs(string begin, int cnt) {
    for (int i = 0; i < Words.size(); i++) {
        if (checked[i] == true) {
            continue;
        }
        int num = 0;
        for (int j = 0; j < Words[i].size(); j++) {
            if (Words[i][j] != begin[j]) {
                num++;
            }
            if (num > 1) {
                break;
            }
        }
        if (num == 1) {
            if (Words[i] == Target) {
                answer = min(answer, cnt + 1);
                return;
            }
            checked[i] = true;
            dfs(Words[i], cnt + 1);
            checked[i] = false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    answer = INF;
    Target = target, Words = words;
    memset(checked, false, sizeof(checked));
    
    if (find(words.begin(), words.end(), target) != words.end()) {
        dfs(begin, 0);
    } else {
        return 0;
    }
    
    return answer;
}