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

1. 문제

코딩테스트 연습 - 단어 변환 | 프로그래머스 (programmers.co.kr)

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

 

2. bfs

이 문제는 주어진 단어에 대한 그래프를 만들고 깊이 우선 탐색을하면 쉽게 문제가 해결된다.

 

begin 단어를 word에 추가하여 맨마지막 인덱스가 src

 

그래프를 만들때 target이랑 같은 단어가 있으면 그 인덱스를 dest로 설정하여

 

dest 가 초기값인 -1 이면 0을 리턴하고 아니면 bfs를 수행항다.

 

이때 만약 src에서 나가는 간선에 dest가 없을시 즉 dist[dest] 가 -1일시 0을 리턴하는것 또한 신경 써야한다.

 

 

#include <string>
#include <vector>
#include <queue>
#include <utility>
 
using namespace std;
 
pair<vector<vector<bool> >, int> makeGraph(string& target, vector<string>& words) {
    vector<vector<bool> > ret(words.size(), vector<bool>(words.size(), false));
    int dest = -1;
    
    for(int i = 0; i < words.size(); i++) 
        if(target.compare(words[i]) == 0) {
            dest = i;
        }
            
    for(int i = 0; i < words.size() - 1; i++) {
        for(int j = i+1; j < words.size(); j++) {
            int count = 0;
            for(int k = 0; k < words[i].size(); k++) {
                if(words[i][k] != words[j][k])
                    count++;
            }
            if(count == 1) {
                ret[i][j] = true;
                ret[j][i] = true;
            }
        }
    }
    
    return make_pair(ret, dest);
}
 
int bfs(int src, int dest, vector<vector<bool> >& adj) {
    vector<int> dist(adj.size(), -1);
    queue<pair<int, int> > q;
    dist[src] = 0;
    q.push(make_pair(dist[src], src));
    
    while(!q.empty()) {
        int cost = q.front().first;
        int here = q.front().second;
        q.pop();
        
        for(int there = 0; there < adj[here].size(); there++) {
            if(dist[there] == -1 && adj[here][there]) {
                dist[there] = cost + 1;
                q.push(make_pair(dist[there], there));
                if(there == dest)
                    break;
            }
        }
    }
    
    return (dist[dest] == -1)? 0: dist[dest];
}
 
int solution(string begin, string target, vector<string> words) {
    words.push_back(begin);
    pair<vector<vector<bool> >, int> adj = makeGraph(target, words);
    if(adj.second == -1)
        return 0;
    return bfs(words.size() - 1, adj.second, adj.first);
}