[PROGRAMMERS] 단어변환(Level3)

yamkim·2020년 10월 14일
0

PROGRAMMERS

목록 보기
2/13

여행경로(Level3)

  • 문제 링크: 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 단어변환

  • 문제 이해
    1. begin을 target으로 바꿀 수 있다면, 가장 최소의 단계 수를 찾는 것입니다.
    2. begin부터 시작한 현재 단어와 단어들(words)을 비교하고 다음 단어를 선택합니다.
    3. 다음 단어의 선택 기준은 현재 단어와 한글자 차이가 나는지 여부입니다.
    4. 한글자 차이가 나는 단어를 현재 단어로 다시 생각하고 이전과 같은 방식을 반복합니다.

  • 알고리즘 구현
    1. compareString구현
    - 가장 먼저, 현재 단어와 다음 선정될 단어가 한글자만 차이나는지 확인하는 함수를 만듭니다.
    - 단어의 길이가 같다면, 각 인덱스 중 다른 값이 있을 때 cnt를 증가시킵니다.
    - 단어의 글자수가 매번 달라질 수도 있기 때문에, 남는 문자열의 길이가 곧 cnt입니다.
    2. 단어를 비교할 범위를 생각합니다. 선택된적 없는 단어를 선택하되, 처음부터 훑어야 합니다.
    3. 따라서, visited를 사용합니다. (주어진 단어가 32개 초과될 수 있으므로 배열로 만듭니다.)
    4. 재귀함수로 들어갈 때, 1을 더하며 조건에 만족하는 경우이므로 1번 변환했음을 기억합니다.
    5. ret이 각 깊이에서 최솟값만 기억하도록 min 함수를 사용합니다.

  • 알고리즘

#include <string>
#include <vector>

using namespace std;

bool compareString(string str1, string str2) {
    int idx1 = 0;
    int idx2 = 0;
    int cnt = 0;
    while (str1[idx1] && str2[idx2]) {
       if (str1[idx1] != str2[idx2])
           ++cnt;
        ++idx1;
        ++idx2;
    }
    while (str1[idx1++])
        ++cnt;
    while (str2[idx2++])
        ++cnt;
    return (cnt == 1 ? true : false);
}

string target;
vector<string> words;
const int INF = 987654321;

int n;

int solve(string word, int visited[50]) {
    if (word == target) return (0);
    
    int ret = INF;
    for (int next = 0; next < n; ++next) {
        if (visited[next]) continue;
        if (!compareString(word, words[next])) continue;
        visited[next] = 1;
        ret = min(ret, 1 + solve(words[next], visited));
        visited[next] = 0;
    }
    return (ret);
}

int solution(string _begin, string _target, vector<string> _words) {
    target = _target;
    words = _words;
    n = words.size();
    
    int visited[50] = { 0, };
    int answer = solve(_begin, visited);
    return (answer == INF ? 0 : answer);
}

0개의 댓글