[Programmers] #43163 - 단어 변환 [Java][C++][Python]

문제 링크

---

1. 아이디어

각 단어를 정점으로 두고 한 글자만 다른 두 단어를 간선으로 잇는 그래프를 생각하면, begin에서 target까지의 최소 변환 횟수는 이 그래프의 최단 경로 길이다. 간선 비용이 모두 1이므로 BFS로 구한다.

어떤 단어의 인접 단어는 각 자리를 a부터 z까지 바꿔 본 후보 중 words에 실제로 존재하는 것이다. words를 미리 집합으로 만들어 두면 후보가 유효한지 빠르게 판별할 수 있다. 큐를 레벨 단위로 비우면서 레벨을 세면 그 값이 곧 변환 단계 수다.

target이 words에 없으면 후보 검사를 통과하지 못해 큐에 들어오지 못하고, 결국 큐가 비어 0을 반환한다.

---

2. 복잡도

접근	시간	공간
풀이	$O(W \times L^2)$	$O(W \times L)$

($W$ = words의 단어 수, $L$ = 단어 하나의 길이. 방문 단어마다 $L$개 자리를 26가지로 바꿔 보고 후보 생성·조회에 각각 $O(L)$이 든다)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        Set<String> dict = new HashSet<>(List.of(words));

        Queue<String> q = new ArrayDeque<>();
        q.offer(begin);

        Set<String> vis = new HashSet<>();
        vis.add(begin);

        int dist = 0;

        while (!q.isEmpty()) {
            int sz = q.size();
            while (sz-- > 0) {
                String cur = q.poll();
                if (cur.equals(target)) return dist;

                for (int i = 0; i < cur.length(); i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        String nxt = cur.substring(0, i) + c + cur.substring(i + 1);
                        if (!dict.contains(nxt) || vis.contains(nxt)) continue;

                        q.offer(nxt);
                        vis.add(nxt);
                    }
                }
            }

            dist++;
        }

        return 0;
    }
}

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

int solution(string begin, string target, vector<string> words) {
    unordered_set<string> dict(words.begin(), words.end());

    queue<string> q;
    q.push(begin);

    unordered_set<string> vis;
    vis.insert(begin);

    int dist = 0;

    while (!q.empty()) {
        int sz = q.size();
        while (sz--) {
            string cur = q.front();
            q.pop();

            if (cur == target) return dist;

            for (int i = 0; i < cur.size(); i++) {
                string nxt = cur;
                for (char c = 'a'; c <= 'z'; c++) {
                    nxt[i] = c;
                    if (!dict.contains(nxt) || vis.contains(nxt)) continue;

                    q.push(nxt);
                    vis.insert(nxt);
                }
            }
        }

        dist++;
    }

    return 0;
}

import string
from collections import deque


def solution(begin, target, words):
    words = set(words)

    q = deque([begin])
    vis = {begin}
    dist = 0

    while q:
        for _ in range(len(q)):
            cur = q.popleft()
            if cur == target:
                return dist

            for i in range(len(cur)):
                for c in string.ascii_lowercase:
                    nxt = cur[:i] + c + cur[i + 1 :]
                    if nxt not in words or nxt in vis:
                        continue

                    q.append(nxt)
                    vis.add(nxt)

        dist += 1

    return 0

---