🐣 문제

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

🐤 풀이

1. queue에 단어와, 그 단어까지 몇 개의 단어를 거쳤는지를 pair로 담았다.
2. queue가 empty일 때 까지,
   2-1. queue에서 하나를 꺼내 단어는 s에 거쳐간 단어 수는 cnt에 담는다.
   2-2. 만약 target을 찾으면 바로 cnt를 return
   2-3. 찾지 않았으면, 한 글자 차이나는지를 확인
   2-4. 한 글자 차이가 나고, 아직 방문하지 않았으면 방문체크 후 queue에 담는다.

🐥 코드

#include <string>
#include <vector>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;

bool visited[51];
int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    memset(visited, false, sizeof(visited));
    
    queue<pair<string, int>> q;
    q.push({begin, 0});
    
    while(!q.empty()){
        string s = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        cout << s << "\n";
        if(s == target) {
            return cnt;
        }
        
        else{      
            for(int i = 0; i < words.size(); i++){
                int diff = 0;
                for(int j = 0; j < words[0].size(); j++)
                    if(words[i][j] != s[j]) diff++;
                if(diff == 1 && !visited[i]){
                    visited[i] = true;
                    q.push({words[i], cnt + 1});
                }
            }
        }
    }
    
    return 0;
}