[프로그래머스]깊이/너비 우선 탐색(DFS/BFS) : 단어 변환 (level 3)(c++)

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

코딩테스트 연습 - 단어 변환

 

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

using namespace std;

// 두 단어의 글자 차이가 1개 나면 true 반환
bool possible(string A, string B)
{
    int dif = 0;
    for (int i = 0; i < A.size(); ++i)
    {
        if (A[i] != B[i])
        {
            ++dif;
        }
    }
    return dif == 1;
}

int bfs(string begin, string target, vector<string> words, int N)
{
    vector<bool> visited(N);
    queue<pair<string, int>> q;
    q.push({begin, 0});

    while (!q.empty())
    {
        string now = q.front().first;
        int cnt = q.front().second;
        q.pop();

        // 목표단어에 도착하면 이동횟수 리턴
        if (now == target)
        {
            return cnt;
        }

        // words벡터의 단어들 중 현재 단어와 글자가 1개 차이나고, 
        // 아직 방문한적 없으면 큐에 push
        for (int i = 0; i < N; ++i)
        {
            if (!visited[i] && possible(now, words[i]))
            {
                visited[i] = true;
                q.push({ words[i], cnt + 1 });
            }
        }
    }
    return 0;
}

int solution(string begin, string target, vector<string> words) {

    // bfs탐색으로 begin부터 target까지 최소 이동횟수 구하기
    return bfs(begin, target, words, words.size());
}

 

 

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.

문제 요구사항과 주요 제약조건을 옮기면 위와 같다.

 

words벡터의 단어로만 이동할 수 있는데 그 벡터의 길이가 작고,

모든 단어의 길이가 같으며, 현재 단어와 다음 단어의 길이가 1차이만 나면 되므로

큐에 다음 단어를 push하는 기준을 다음과 같은 함수를 통해 처리할 수 있다.

// words벡터의 단어들 중 현재 단어와 글자가 1개 차이나고, 
// 아직 방문한적 없으면 큐에 push
for (int i = 0; i < N; ++i)
{
    if (!visited[i] && possible(now, words[i]))
    {
        visited[i] = true;
        q.push({ words[i], cnt + 1 });
    }
}

...

// 두 단어의 글자 차이가 1개 나면 true 반환
bool possible(string A, string B)
{
    int dif = 0;
    for (int i = 0; i < A.size(); ++i)
    {
        if (A[i] != B[i])
        {
            ++dif;
        }
    }
    return dif == 1;
}