(프로그래머스 c++)단어변환

DFS, BFS 두 방법으로 풀 수 있는 문제다.

본인은 BFS로 풀었다..!

 

우선 큐를 만들어 준다. 단어를 탐색하고, 해당 단어의 인덱스까지 pair로 묶어주어 q에 넣어준다.

tmp_q는 임시 큐로 단계를 올릴 때 사용한다.

그리고 answer는 1로 초기화 하였다.

1단계의 단어를 바로 찾기 때문에 1로 초기화 하였다.

 

우선 words에 target이 있는지 확인한다. 없으면 바로 0 리턴.

target이 words 안에 있다면 탐색을 시작한다.

1단계의 단어를 탐색하기 위해 0 ~ words.size()만큼 반복한다.

그리고 count를 이용하여 begin과 words[i]를 비교하여 한 개의 알파벳을 바꿀 수 있는지 확인한다.

count가 begin.size() - 1 이라면 한 개의 알파벳을 바꿀 수 있다는 뜻이므로

해당 단어와 인덱스를 pair로 묶어 q에 넣어준다.

 

1단계 탐색이 끝났으면 이제 단계를 높여가며 단어를 찾도록 한다.(BFS)

큐가 비어있을 때까지 while문을 반복.

q에 담겨져 있는 pair를 꺼내기 위해 pair<string, int> p를 선언하였고,

p.first에는 단어, p.second에는 단어의 위치를 가지게 된다.

만약 string str은 p.first를 나타내고, str이 target과 같다면 answer을 리턴해주도록 한다.

 

str이 target과 같지 않다면 탐색을 시작한다.

탐색 방법은 1단계에서 진행했던 방법과 같다.

단, q에 넣는 것이 아니라 tmp_q에 단어와 인덱스를 넣어준다.

q가 비어있으면 해당 단계는 끝난 상태이므로 if문을 통해

answer++을 실행하고, tmp_q에 있던 데이터를 q에 옮겨주도록 한다.

빠져나오기 전 tmp_q는 모두 pop()을 하여 비워주어야 한다..!

 

이렇게 하면 BFS로 문제를 풀 수 있다.

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

using namespace std;

int solution(string begin, string target, vector<string> words) {
    int answer = 1;
    queue<pair<string, int>> q;
    queue<pair<string, int>> tmp_q;
    
    if(find(words.begin(), words.end(), target) == words.end())
        return 0;
    
    for(int i = 0; i < words.size(); i++)
    {
        int count = 0;
        
        for(int j = 0; j < begin.size(); j++)
        {
            if(begin[j] == words[i][j])
                count++;
        }
        
        if(count == begin.size() - 1)
            q.push(make_pair(words[i], i));
    }
    
    while(!q.empty())
    {
        pair<string, int> p;
        p = q.front();
        q.pop();
        string str = p.first;
        
        if(str == target)
            return answer;
        
        for(int i = p.second + 1; i < words.size(); i++)
        {
            int count = 0;
            
            for(int j = 0; j < str.size(); j++)
            {    
                if(str[j] == words[i][j])
                    count++;
            }
            
            if(count == str.size() - 1)
                tmp_q.push(make_pair(words[i], i));
        }
        
        if(q.empty())
        {
            q = tmp_q;
            answer++;
            while(!tmp_q.empty())
                tmp_q.pop();
        }
    }
    return answer;
}