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

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

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

 

#include <string>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <map>
#include <queue>
using namespace std;
 
void findNeighbor(string s, vector<string>& words, vector<string>& neighbors){
    neighbors.clear();
    int i,j;
    int count;
    int len=words[0].length();
    for (i=0; i<words.size(); i++){
        count=0;
        if (s.compare(words[i])!=0){
            for (j=0; j<len; j++){
                if (words[i][j]-s[j]==0){
                    count+=1;
                }
            }
            if (count==len-1){
                neighbors.push_back(words[i]);
            }
        }
    }
}
 
 
int solution(string begin, string target, vector<string> words) {
    map<string, int> visited;
    vector<string> neighbors;
    queue<string> q;
    int len=words[0].length();
    if (find(words.begin(), words.end(), target)==words.end()){
        return 0;
    }
    for (int i=0; i<words.size(); i++){
        visited[words[i]]=0;
    }
    q.push(begin);
    visited[begin]=1;
    while (!q.empty()){
        string x=q.front();
        q.pop();
        findNeighbor(x, words, neighbors);
        for (int i=0; i<neighbors.size(); i++){
            string y=neighbors[i];
            if (visited[y]==0){
                q.push(y);
                visited[y]=visited[x]+1;
            }
        }
    }
    return visited[target]-1;
}

BFS 로 풀었다

좀 복잡하고 어렵고 코드 가독성이 gg다(오랜만에 코테 공부해서 그런가 더 나아질거라 믿는다)

 

1. words 목록에 target 없으면 0 리턴 후 종료

2. 그렇지 않으면 큐에 begin 넣어주고, visited에 1 해서 이동 거리를 나타낸다

3. 큐에서 다음 과정을 반복한다:

큐의 맨 첫번째 아이템을 pop하고, 그 단어의 neighbor 목록을 찾아, 방문하지 않은 neighbor 단어에 한해서만 큐에 push하고

이동거리+1 해서 visited를 표시한다

4. 큐가 비면 target 의 이동거리-1 해서 답을 구해준다

 

 

너무 어렵게 구한 것 같아 다른 분들의 풀이를 보니까

int visited[50];
 
int possible(string a, string b)
{
    int i;
    int cnt = 0;
 
    for(i=0;i<a.length();i++)
    {
        if(a[i] != b[i]) cnt++;
    }
 
    if(cnt==1) return 1;
    else return 0;
}
 
int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    queue<pair<string,int>> Q;
    int i;
    string temp;
    int num;
 
    Q.push(make_pair(begin,0));
    while(!Q.empty())
    {
        temp = Q.front().first;
        num = Q.front().second;
        Q.pop();
 
        if(temp.compare(target) == 0)
        {
            answer = num;
            break;
        }
 
        for(i=0;i<words.size();i++)
        {
            if(visited[i]) continue;
            if(possible(temp, words[i]))
            {
                visited[i] = 1;
                Q.push(make_pair(words[i],num+1));
            }
        }
    }
 
    return answer;
}