프로그래머스 (C/C++) 43163 : 단어 변환

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

프로그래머스

---

풀이

begin에서 한 자리씩 바꿔가며 풀려 했는데, 어떤 위치를 어떤 알파벳으로 바꿔야 할지 감이 오지 않았다.

그래서 words를 순회하며 현재 단어와 한 자리와 다른 경우 큐에 넣어 계속 탐색을 시행했다.

begin을 시작으로 탐색했으며 map<word, cnt> visited 로 방문했던 노드를 확인해 중복 탐색을 제거했다.

---

코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

int getDifferentCnt(string base, string target) {
    int cnt = 0;
    for (int i = 0; i < base.size(); i++) 
        cnt += base[i] != target[i];
    return cnt;
}

int solution(string begin, string target, vector<string> words) {
    
    // target이 words에 없음
    if (find(words.begin(), words.end(), target) == words.end())
        return 0;
    
    unordered_map<string, int> visited;
    queue<pair<string, int>> q;
    
    q.push({begin, 0});
    while (!q.empty()) {
        auto [str, cnt] = q.front();
        q.pop();
        
        for (string word : words) {
            
            // 1자리만 다르지 않음 || 이미 확인한 단어
            if (getDifferentCnt(str, word) != 1 
            	|| visited.find(word) != visited.end()) continue;
            
            // 현재 단어 == target
            if (word == target)
                return cnt + 1;
            
            // 방문 처리 후 큐에 삽입
            visited[word] = 1;
            q.push({word, cnt + 1});
        }
    }
    return 0;
}