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

문제 링크

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

프로그래머스

 

 

코드 구현

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

using namespace std;

bool IsNeighbor(const string& a, const string& b)
{
    // 두 단어를 비교하여 하나만 단어가 다른 경우를 찾음
    int diff = 0;
    for (int i = 0; i < a.size(); ++i)
    {
        if (a[i] != b[i]) diff++;
        if (diff > 1) return false;
    }

    return true;
}

int solution(string begin, string target, vector<string> words) 
{
    int n = words.size();

    vector<bool> visited(n, false);
    queue<pair<string, int>> q;

    // 현재 단어와 카운트를 큐에 삽입
    q.push({ begin, 0 });
    
    // bfs 순회
    while (!q.empty())
    {
        pair<string, int> now = q.front();

        string currentStr = now.first;
        int count = now.second;

        q.pop();

        if (currentStr == target) return count;

        // 방문하지 않고 단어가 하나만 다른 단어를 큐에 삽입
        for (int i = 0; i < n; ++i)
        {
            if (!visited[i] && IsNeighbor(currentStr, words[i]))
            {
                visited[i] = true;
                q.push({ words[i], count + 1 });
            }
        }
    }

    return 0;
}

 

 

해결 방법

• 가장 짧은 변환 과정을 찾으므로 bfs 이용
• words 안에 있는 단어 중 한 번에 하나의 알파벳만 바꿀 수 있으므로 알파벳이 하나만 다른 단어들을 다음에 순회할 노드라고 생각하고 큐에 삽입
• 큐를 순회하며 카운트 값 증가