[프로그래머스 43163] 단어 변환

AlgorithmBFS

문제

단어 begin에서 target으로 변환한다. 한 번에 한 글자만 바꿀 수 있고, 변환 결과는 반드시 words 목록에 있어야 한다. 최소 변환 단계를 반환하고, 변환 불가능하면 0을 반환한다.

핵심

각 단어를 노드로, 한 글자 차이 관계를 간선으로 보면 그래프 최단 경로 문제다. 가중치가 동일하므로 BFS를 쓴다.

풀이

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

bool canConvert(const string& a, const string& b) {
    int diff = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        if (a[i] != b[i]) diff++;
    }
    return diff == 1;
}

struct Node { int idx; int dist; };

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

    queue<Node> q;
    for (int i = 0; i < n; i++) {
        if (canConvert(begin, words[i])) {
            visited[i] = true;
            q.push({i, 1});
        }
    }

    while (!q.empty()) {
        auto [idx, dist] = q.front();
        q.pop();

        if (words[idx] == target) return dist;

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            if (!canConvert(words[idx], words[i])) continue;

            visited[i] = true;
            q.push({i, dist + 1});
        }
    }
    return 0;
}

메모

  • 그래프 모델링
    • 단어를 노드, 한 글자 차이를 간선으로 본다. begin은 words에 없을 수 있으므로 별도 시작점으로 처리한다
    • canConvert는 두 단어의 글자 차이가 정확히 1인지 확인한다. 모든 단어의 길이가 같다는 조건이 있으므로 길이 체크는 불필요하다
  • BFS 패턴
    • visited는 push할 때 찍는다. 자세한 이유는 BFS에서 visited를 push할 때 찍어야 하는 이유 참고
    • begin에서 한 글자 차이인 단어들을 모두 초기 큐에 넣는다. begin 자체는 words의 인덱스가 아니므로 visited 배열에 포함되지 않는다
    • 목적지 도달 즉시 return dist로 빠져나온다
  • 복잡도 특성
    • 단어 수 N ≤ 50, 단어 길이 L ≤ 10이다. 간선 판별이 O(N²·L)이지만 충분히 작다
    • N이 크다면 와일드카드 패턴(예: h*t, *ot)으로 인접 리스트를 미리 구축하는 방법이 있다

복잡도

풀이시간공간
BFSO(N²·L)O(N)