[PG / C++] 프로그래머스 단어 변환

문제

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

 

---

풀이

1. 백트래킹을 이용한 풀이

target 단어가 words에 포함되어 있지 않으면 종료 (set에 저장해서 find로 찾기)

백트래킹을 사용해서 begin > target까지의 단어 변환 모든 과정 찾기

• ⭐️ 이때 변환 횟수가 최솟값이 아니면 종료해서 탐색 과정 줄이기
• 최소 변환 과정이므로, 이미 한 번 사용한 단어는 재사용하지 않음 (visited[idx]로 처리)
• checkValid 함수로 알파벳 한 개 이상 차이가 나는 단어인지 확인 (변환 조건 충족 여부 확인)

#include <string>
#include <vector>
#include <iostream>
#include <set>

using namespace std;
int answer = 54;
int visited[54];

bool checkValid(string cur, string next){
    int cnt = 0;
    // 현재 단어에서 1개 알파벳보다 많이 차이나는지 확인
    for(int i=0; i<cur.size(); i++){
        if(cur[i] != next[i]){
            cnt++;
            // 1개 이상 차이나면 변환 불가
            if(cnt > 1){
                return false;
            }
        }
    }
    return true;
}

void backTracking(string cur, string target, vector<string> words, int depth){
    // 최단이 아닌 경우 제외
    if(depth > answer){
        return;
    }
    // 타겟 단어와 같으면 종료
    if(cur == target){
        answer = depth;
        return;
    }
    
    for(int i=0; i<words.size(); i++){
        // 이미 탐색한 단어면 제외
        if(visited[i]){
            continue;
        }
        // 알파벳 1개 이상 차이나는 경우 제외
        if(!checkValid(cur, words[i])){
            continue;
        }
        // 방문처리
        visited[i] = 1;
        // 탐색
        backTracking(words[i], target, words, depth+1);
        // 원복
        visited[i] = 0;
    }
}

int solution(string begin, string target, vector<string> words) {

    set<string> s;
    
    for(auto word: words){
        s.insert(word);
    }
    
    // 단어 집합에 타겟 단어가 없는 경우 종료
    if(s.find(target) == s.end()){
        return 0;
    }
    
    backTracking(begin, target, words, 0);
    
    
    return answer;
}

 

2.  BFS 이용 풀이

위 풀이에서 최악의 경우 O(n!) (n은 단어의 개수)까지 시간복잡도가 나온다.

최단 변환 과정을 찾아야하므로, BFS를 이용해서 다시 코드를 작성해봤다. 

*BFS의 경우 O(N^2) 의  시간복잡도가 나온다. 

 

queue<pair<string, int>> : 큐에 단어와 해당 단어까지 변환 횟수 depth를 함께 저장

 

그 외 코드는 일반적인 bfs와 동일하고, 종료 조건 및 탐색 조건도 백트래킹 코드에서 사용한 것과 같다

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <queue>

using namespace std;
int answer = 54;
int visited[54];

bool checkValid(string cur, string next){
    int cnt = 0;
    // 현재 단어에서 1개 알파벳보다 많이 차이나는지 확인
    for(int i=0; i<cur.size(); i++){
        if(cur[i] != next[i]){
            cnt++;
            // 1개 이상 차이나면 변환 불가
            if(cnt > 1){
                return false;
            }
        }
    }
    return true;
}

void bfs(string begin, string target, vector<string> words){
    queue<pair<string, int>> q; // 단어, depth 저장
    q.push({begin, 0});
    
    while(!q.empty()){
        string cur = q.front().first;
        int depth = q.front().second;
        q.pop();
        
        // 타겟 단어라면 종료
        if(cur == target){
            answer = depth;
            return;
        }
        
        // 다음 단어 탐색
        for(int i=0; i<words.size(); i++){
            // 사용한적 있거나, 알파벳 조건을 만족하지 않는 경우 제외
            if(visited[i] || !checkValid(cur, words[i])){
                continue;
            }
            visited[i] = 1;
            q.push({words[i], depth+1});
        }
    }
}

int solution(string begin, string target, vector<string> words) {

    set<string> s;
    
    for(auto word: words){
        s.insert(word);
    }
    
    // 단어 집합에 타겟 단어가 없는 경우 종료
    if(s.find(target) == s.end()){
        return 0;
    }
    bfs(begin, target, words);
    
    
    return answer;
}