[level 3] 단어 변환 - 43163

[level 3] 단어 변환 - 43163

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

프로그래머스

처음으로 시도한 3 레벨 문제이지만 사실문제를 다 풀고 나서 3 레벨인걸 확인했습니다.

BFS 원리를 이해하고 있으면 생각보다 쉽게 접근이 가능했습니다.

[level 3] 단어 변환 - 43163 풀이코드

#include<bits/stdc++.h>
using namespace std;

string s;
int cnt;
int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    bool isExist = false;
    for (string i : words) 
    {
        if (i == target) 
        {
            isExist = true;
            break;
        }
    }
    
    if (!isExist) return 0;
    
    queue<pair<string, int>> q;
    q.push({begin, 0});
    while(q.size())
    {
        tie(s, cnt) = q.front(); q.pop();
        for (int i = 0; i < words.size(); i++) 
        {
            int temp = 0;
            for (int j = 0; j < s.length(); j++)
            {
                if (s[j] != words[i][j]) temp++;
                if (temp > 1) break;
            }
            
            if (temp == 1)
            {
                if (words[i] == target) return cnt + 1;
                else q.push({words[i], cnt + 1});
            }
        }
    }
    
    return answer;
}