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

🔐 프로그래머스 - 단어 변환

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

🔑 풀이

두 개의 단어가 주어졌을 때, 한 단어가 목표 단어로 도달할 수 있는지를 물어보는 문제이다.

우선, 주어진 배열 words 안에 목표 단어가 들어있는지를 확인해야 한다.

auto it = find(words.begin(), words.end(), target);
int targetIdx = it - words.begin();
    
if (*it != target) return 0;

변환 과정에서 한 번에 한 개의 알파벳만 바꿀 수 있다고 했으므로, 문자가 하나씩만 다른 단어들을

그래프처럼 연결해야 한다. words 배열 안의 문자의 길이는 모두 같다고 했으므로, 단어의 각

문자끼리를 비교하여 하나만 문자가 틀리다면, 서로 변환이 가능한 문자일 것이다.

bool connect(string& a, string& b) {
    int cnt = 0;
    for (int i = 0; i < a.length(); ++i) {
        if (a[i] != b[i]) cnt++;
    }
    
    if (cnt == 1) return true;
    else return false;
}

주어진 words 배열 안에 시작 단어를 넣고, 모든 단어들에 대해 서로 connect 함수를 통해

인접 리스트를 만들고, BFS를 돌려주었다.

🧩 코드