[알고리즘 문제] BFS - 프로그래머스 단어 변환(level 3)

문제 이해

begin에서 시작해 한 번에 알파벳 하나만 바꾸면서 target에 도달해야 합니다. 변환한 단어는 반드시 words 안에 있어야 하며, 가능한 변환 과정 가운데 단계 수가 가장 적은 값을 반환합니다.

begin  = "hit"
target = "cog"
words  = ["hot", "dot", "dog", "lot", "log", "cog"]

hit → hot → dot → dog → cog
최소 변환 횟수: 4

target이 words에 없다면 규칙상 마지막 변환을 수행할 수 없습니다. 이 경우에는 탐색할 필요 없이 바로 0을 반환할 수 있습니다.

단어를 그래프로 모델링

문제의 요소를 그래프 용어로 바꾸면 탐색 방법이 선명해집니다.

노드: begin과 words의 각 단어
간선: 두 단어가 정확히 한 글자만 다를 때 존재
간선 비용: 변환 한 번이므로 모두 1
목표: begin에서 target까지의 최단 거리

모든 변환의 비용이 같으므로 이 그래프는 가중치 없는 그래프로 볼 수 있습니다. 따라서 가까운 단계부터 탐색하는 BFS를 사용하면 처음 target을 발견한 거리가 최소 변환 횟수입니다.

한 글자 차이 판별하기

두 단어의 같은 위치를 차례로 비교하고 다른 문자의 수를 셉니다. 차이가 정확히 하나일 때만 한 번의 변환으로 이동할 수 있습니다.

bool canTransform(const string& first, const string& second)
{
    int differenceCount = 0;

    for (int i = 0; i < static_cast<int>(first.size()); ++i) {
        if (first[i] == second[i]) {
            continue;
        }

        ++differenceCount;

        if (differenceCount > 1) {
            return false;
        }
    }

    return differenceCount == 1;
}

초고에서는 같은 문자의 수가 길이 - 1인지 검사했습니다. 제한사항상 모든 단어 길이가 같으므로 그 방식도 맞습니다. 최종 코드에서는 함수 이름과 직접 대응하도록 다른 문자의 수를 세고, 두 글자 이상 다르면 즉시 종료하도록 표현했습니다.

첫 접근: 그래프 미리 만들기

처음에는 begin과 words를 하나의 노드 배열에 담고 모든 단어 쌍을 비교했습니다. 한 글자만 다른 쌍을 찾으면 양방향 인접 리스트에 간선을 추가합니다.

vector<string> nodes = {begin};
nodes.insert(nodes.end(), words.begin(), words.end());

vector<vector<int>> graph(nodes.size());

for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
    for (int j = i + 1; j < static_cast<int>(nodes.size()); ++j) {
        if (canTransform(nodes[i], nodes[j])) {
            graph[i].push_back(j);
            graph[j].push_back(i);
        }
    }
}

이 방식은 그래프 구조와 BFS가 분리되어 있어 생각한 모델을 코드에서 그대로 확인하기 쉽습니다. 단어 수를 N, 단어 길이를 L이라 하면 그래프 생성에 O(N²L) 시간이 필요합니다.

BFS로 최소 변환 횟수 찾기

distance[i]는 begin부터 nodes[i]까지의 최소 변환 횟수입니다. -1은 아직 방문하지 않았다는 뜻이고, 시작 단어의 거리는 0입니다.

distance[0] = 0;
q.push(0);

while (!q.empty()) {
    int current = q.front();
    q.pop();

    for (int next : graph[current]) {
        if (distance[next] != -1) continue;

        distance[next] = distance[current] + 1;

        if (next == targetIndex) {
            return distance[next];
        }

        q.push(next);
    }
}

BFS는 변환 횟수가 적은 노드부터 방문합니다. 따라서 목표 단어를 처음 발견한 순간의 거리가 최단 거리이며 즉시 반환해도 됩니다. 큐에 넣을 때 거리를 기록하므로 같은 단어가 여러 경로에서 중복으로 들어가는 것도 막을 수 있습니다.

그래프를 저장하지 않는 개선

인접 리스트를 먼저 만들지 않아도 됩니다. 큐에서 단어를 하나 꺼낼 때마다 아직 방문하지 않은 모든 단어와 비교해, 한 글자만 다르면 바로 다음 탐색 대상으로 추가할 수 있습니다.

while (!q.empty()) {
    int current = q.front();
    q.pop();

    for (int next = 0; next < static_cast<int>(nodes.size()); ++next) {
        if (distance[next] != -1) continue;
        if (!canTransform(nodes[current], nodes[next])) continue;

        distance[next] = distance[current] + 1;
        q.push(next);
    }
}

최악의 시간복잡도는 여전히 O(N²L)이지만 별도의 간선 저장 공간이 필요 없어 추가 공간을 O(N)으로 줄일 수 있습니다. 단어가 최대 50개이고 길이가 최대 10이므로 모든 후보를 직접 비교해도 충분히 빠르며 코드도 더 짧습니다.

그래프를 미리 만드는 방식은 연결 관계를 여러 번 재사용할 때 유리하고, 탐색 중 비교하는 방식은 이 문제처럼 한 번만 탐색하며 입력이 작을 때 간결합니다.

최종 코드

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

using namespace std;

bool canTransform(const string& first, const string& second)
{
    int differenceCount = 0;

    for (int i = 0; i < static_cast<int>(first.size()); ++i) {
        if (first[i] == second[i]) {
            continue;
        }

        ++differenceCount;

        if (differenceCount > 1) {
            return false;
        }
    }

    return differenceCount == 1;
}

int solution(string begin, string target, vector<string> words)
{
    if (find(words.begin(), words.end(), target) == words.end()) {
        return 0;
    }

    vector<string> nodes = {begin};
    nodes.insert(nodes.end(), words.begin(), words.end());

    vector<int> distance(nodes.size(), -1);
    queue<int> q;

    distance[0] = 0;
    q.push(0);

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (int next = 1; next < static_cast<int>(nodes.size()); ++next) {
            if (distance[next] != -1) {
                continue;
            }

            if (!canTransform(nodes[current], nodes[next])) {
                continue;
            }

            distance[next] = distance[current] + 1;

            if (nodes[next] == target) {
                return distance[next];
            }

            q.push(next);
        }
    }

    return 0;
}

목표 단어가 목록에 있는지 먼저 검사한 뒤, BFS에서는 인덱스 대신 단어 자체로 목표 도달을 확인합니다. 목표를 발견하지 못한 채 큐가 비면 가능한 변환 경로가 없으므로 0을 반환합니다.

복잡도와 확장 방법

• 시간복잡도는 O(N²L)
• 최대 N개의 단어를 큐에서 꺼내고, 매번 최대 N개 후보의 L글자를 비교합니다.
• 추가 공간복잡도는 O(N)
• 단어 배열 외에 거리 배열과 BFS 큐가 단어 수에 비례하는 공간을 사용합니다.
• 차이는 정확히 한 글자여야 한다
• 같은 단어는 변환 한 단계가 아니며, 두 글자 이상 다른 단어도 직접 이동할 수 없습니다.
• 목표 단어의 존재를 먼저 검사한다
• target이 words에 없으면 문제의 변환 규칙상 도달할 수 없습니다.
• 입력이 커지면 패턴 인덱스를 고려한다
• hot을 *ot, h*t, ho*처럼 바꾼 패턴별로 단어를 묶으면 이웃 후보를 더 빠르게 찾을 수 있습니다.

정리

• 각 단어를 노드, 한 글자 차이인 변환 관계를 간선으로 본다.
• 모든 변환 비용이 같으므로 BFS로 최소 변환 횟수를 구한다.
• 거리 배열의 -1로 미방문 상태를 표현한다.
• 목표 단어를 처음 발견한 순간의 거리가 최단 거리다.
• 입력 제한이 작으므로 그래프를 저장하지 않고 탐색 중 단어를 비교해도 충분하다.

처음에는 문제의 변환 규칙대로 모든 단어 사이의 간선을 직접 만들었습니다. 그 덕분에 문제가 가중치 없는 최단 거리 탐색이라는 사실을 분명히 볼 수 있었습니다. 이후에는 그래프가 반드시 자료구조로 미리 존재할 필요는 없고, 필요한 순간에 이웃을 판별할 수도 있다는 점을 배웠습니다.