[프로그래머스](DFS/BFS) 단어 변환 (C++)

단어 변환(Level 3)

문제

전체 문제 보기

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

접근법

각 단어를 하나의 노드로 간주한다면 "변환 가능한 단어"라는 말은 "이동 가능한 노드"라는 개념으로 볼 수 있다. 결국 이 문제는 그래프에서 길 찾기 문제와 본질적으로 같다. 다만, 노드가 알파벳으로 구성된 단어라는 점이 일반적인 길 찾기와의 차이점이다. 때문에 이 문제에서는 임의의 두 노드가 서로 이동 가능한 노드인지를 구분하기 위한 별도의 방법이 필요하다. 문제의 설명에서 두 단어의 알파벳이 하나만 다를 경우 변환 가능하다고 했다. 즉, 알파벳 하나만 다른 노드는 이동 가능한 노드라는 말이다. 이 부분을 추가적으로 구현한다면 기본적인 BFS와 동일하게 풀 수 있다.

 

BFS를 활용한 길찾기에 대해서 더 알고 싶다면 아래의 글을 참고하자.

• 그래프, DFS, BFS 기본 개념 (C 언어)

choisb/Study-DataStructure

• BFS를 통한 길찾기 예제(C++ 언어)

4장 인공지능 - ② 길 찾기 알고리즘

구현

두 노드가 서로 인접한 노드인지 확인하기 위해서 IsExchangeable 함수를 주목해서 보자. 이 외의 다른 부분들은 일반적은 BFS 구현과 동일하기 때문에 자세한 설명은 주석으로 대체한다.

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

using namespace std;

// Node는 문자와 깊이를 가진다.
struct Node{
    Node(const string& str)
    :depth(0)
    ,word(str)
    {
    }

    string word;
    int depth = 0;
};

// 두 개의 문자가 바꿀 수 있는 관계인지 반환 
bool IsExchangeable(const string& left, const string& right)
{
    int diff = 0;
    for(int i = 0; i < left.size(); ++i)
        if(left[i] != right[i])
            diff++;

    return diff == 1;
}

// bfs 실행. 탐색 깊이를 반환
int bfs(const string& begin, const string& target, const vector<Node*>& nodes)
{  
    queue<const Node*> q;
    const Node* curNode;

    // queue에 초기값 삽입(begin 과 바로 인접한 노드들)
    for(auto node : nodes)
    {
        if(IsExchangeable(begin, node->word))
        {
            // 첫 탐색이기 때문에 깊이는 모두 1이다
            node->depth = 1;
            q.emplace(node);
        }
    }

    // 탐색 시작
    // 큐가 비었다는 것은 모든 경우의 수를 다 따져봤지만 변환할 방법이 없다는 뜻.
    while(!q.empty())
    {
        // 큐의 첫번째 노드를 꺼내서 확인한다.
        curNode = q.front();
        q.pop();

        // 목표를 찾았다면 curNode의 깊이를 반환한다.
        if(curNode->word.compare(target) == 0)
            return curNode->depth;

        // 현재 노드에서 변환가능하며 큐에 삽입된적 없는 노드를 모두 큐에 삽입한다.
        for(auto node : nodes)
        {
            if(IsExchangeable(curNode->word, node->word) && node->depth == 0)
            {
                // 새로 큐에 삽입되는 노드의 깊이는 현재 노드의 다음 노드이기 때문에
                // 현재 노드 깊이의 +1 값이다.
                node->depth = curNode->depth + 1;
                q.emplace(node);
            }
        }
    }    
    return 0;
}

int solution(string begin, string target, vector<string> words) 
{     
    int answer = 0;
    vector<Node*> nodes;

    // words를 활용해서 nodes 벡터 생성
    for(auto word : words)
    {
        Node* nNode = new Node(word);
        nodes.emplace_back(nNode);
    }

    // bfs 결과값 반환
    answer = bfs(begin, target, nodes);

    // 동적할당한 node들 삭제
    for(auto node : nodes)
    {
        delete node;
    }

    return answer;
}