[프로그래머스/Level 3] 단어 변환 (C++)

programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

레벨3 문제 치고는 어렵지 않은 DFS/BFS 문제였습니다. begin 문자열이 words 배열의 문자열중 어느 문자열로 바뀔 수 있는지를 잘 구현만 한다면 쉽게 해결할 수 있을 것 같습니다.

 

/* BFS 풀이 */

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

bool visit[50];

int solution(string begin, string target, vector<string> words) {
    // 벡터 words에 target이 없는 경우 0을 리턴하고 종료
    if(find(words.begin(), words.end(), target) == words.end()) return 0;
    
    queue<pair<string, int> > q;
    q.push({begin, 0});
    
    while(!q.empty()) {
        string now = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        // 현재 문자열이 target과 같다면 cnt를 리턴하고 종료
        if(now == target) return cnt;
        
        
        for(int i = 0; i < words.size(); i++) {
            int diff = 0;
            // 현재 문자열과 words[i]의 문자열을 한자씩 비교
            for(int j = 0; j < words[i].size(); j++) {
                if(now[j] != words[i][j]) diff++;
                if(diff == 2) break;
            }
            
            // 만약 변환된 적 없는 문자열이면서, diff(다른 문자)가 1이라면 변환 가능
            if(!visit[i] && diff == 1) {
                q.push({words[i], cnt + 1});
                visit[i] = true;
            }
        }
    }
}

 

/* DFS 풀이 */

#include <string>
#include <vector>
using namespace std;

int answer = 100;
bool visit[50];

void DFS(string now, int cnt, string target, vector<string> words) {
    if(now == target) {
        answer = min(answer, cnt);
        return;
    } else {
        for(int i = 0; i < words.size(); i++) {
            int diff = 0;
            for(int j = 0; j < words[i].size(); j++) {
                if(now[j] != words[i][j]) diff++;
                if(diff == 2) break;
            }
            if(!visit[i] && diff == 1) {
                visit[i] = true;
                DFS(words[i], cnt + 1, target, words);
                visit[i] = false;
            }
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    DFS(begin, 0, target, words);
    if(answer == 100) return 0;
    return answer;
}