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

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

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

 

기본적인 아이디어.

 

1. 단어에 한 문자만 틀리면 엣지를 연결하는 그래프를 생성한다.

2. 해당 그래프를 BFS(DFS역시 가능)를 이용하여 begin 과 target 사이 최단 거리(엣지 개수)를 구한다.

 

 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

bool onecheck(string a, string b)
{
    int x=0;
    for(int i=0; i<a.size(); i++)
    {
        if(a[i]!=b[i])
        {
            x++;
        }
        
        if(x>1) break;
    }
    
    if(x>1) return 0;
    else if(x==1) return 1;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    int n=begin.size();
    
    int zz=0;

    
    
    words.insert(words.begin(), target);
    words.insert(words.begin(), begin);
    int size=words.size();
    
    queue <int> q;
    vector <int> w[size];
    int visit[size];
    int d[size];
    
    
    
    
    for(int i=0; i<size; i++)
    {
        for(int j=0; j<size; j++)
        {
            if(i==j) continue;
            
            if(onecheck(words[i] , words[j]))
            {
                w[i].push_back(j);
            }
        }
    }
    
    for(int i=0; i<size; i++)
    { 
        visit[i]=0;
        d[i]=0;
    }

        int start;
        int i=0;

        start=i;
        while(1) 
        {
            
            visit[start]=1;
            for(int j=0; j<w[start].size(); j++)
            {
                if(visit[w[start][j]]==1) continue;
                
                
                                
                q.push(w[start][j]);
                d[w[start][j]]=d[start]+1;
                
                if(w[start][j]==1) return d[start]+1;
            }
            
            if(q.empty())
            {
                answer = 0;
                break;    
            }
            
            
            
            start=q.front();
            q.pop();
        }
        
        
        
    
    
    
    return answer;
}

 

 

프로그래머스 단어 변환 실행시간