99클럽 코테스터디 33일차 TIL 프로그래머스- 단어 변환

단어 변환

프로그래머스 Level 3 Dfs / Bfs
문제 링크

프로그래머스

 

문제 설명

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

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

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 
"hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

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

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

문제를 보고 완전탐색을 하면 되겠다는 생각을 직관적으로 했다.
각 단어의 최대길이는 10이고 words의 최대 길이는 50정도 이기에, 모든 경우의 수를 다 따져도 시간적으로 문제가 없을 것이라 판단했다.

 

문제 풀이

 

완전탐색으로 풀이했다
words 벡터의 맨 끝에 begin 단어를 넣어주고, 현재 위치를 벡터의 끝으로 잡아 탐색 시작지점을 잡아줬다.

 

코드

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

using namespace std;

bool visited[52] = {false, };
int answer = 1e9;

bool canSwitch(string cur, string next) {
    int cnt = 0;
    for (int i=0; i<cur.size(); i++) {
        if (cur[i] != next[i]) cnt++;
    }
    return cnt == 1 ? true : false;
}

void dfs (int cur, int turn, string goal, vector<string> words) {
    if (goal == words[cur]) {
        answer = min(answer, turn);
        return ;
    }
    for (int i=0; i<words.size()-1; i++) {
        if (i != cur && !visited[i] && canSwitch(words[cur], words[i])) {
            visited[i] = true;
            dfs(i, turn+1, goal, words);
            visited[i] = false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    words.push_back(begin);
    if (find(words.begin(), words.end(), target) == words.end()) return 0;

    dfs(words.size()-1, 0, target, words);

    return answer;
}

 

회고

 

그래프를 탐색하는 방식으로 문자열들의 배열을 탐색하게 될줄은 몰랐다.
그래프는 연결성이 있어야만 그래프가 아니라 그래프의 특성을 띄게 만들 수 있으면 그래프로 만들 수 있다는 것을 알수있었다.