단어 변환

문제

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

코드

cpp

#include <string>
#include <vector>
#include<algorithm>
using namespace std;

vector<int> visit(50,0);
vector<int> answers;
void dfs(string begin, string target, vector<string> words,int d){
    if(begin==target){
        answers.push_back(d);
        return;
    }
    if(d==words.size()){
        return;
    }
    
    for(int i=0;i<words.size();i++){
        if(visit[i]==1) continue;
        int cnt=0;
        for(int j=0;j<begin.size();j++){          
            if(begin[j]!=words[i][j]) cnt++;
        }
        if(cnt==1){
            visit[i]=1;
            dfs(words[i],target,words, d+1);
            visit[i]=0;
        }   
    }
    
}
int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    dfs(begin, target,  words,0);
    if(answers.empty()) return 0;
    answer=*min_element(answers.begin(),answers.end());
    return answer;
}

python

from collections import deque,defaultdict

def canTransform(word1,word2):
    cnt=0
    size=len(word1)
    for i in range(size):
        if word1[i]==word2[i]:
            cnt+=1
            
    return True if size-cnt==1 else False


def bfs(begin,target,words):
    q=deque()
    q.append(begin)
    dist=defaultdict(int)
    
    while q:
        now=q.popleft()

        if now==target:
            return dist[target]
        
        for next in words:
                   
            if now==next or not canTransform(now,next) or dist[next]!=0:
                continue
            dist[next]=dist[now]+1
            q.append(next)
    
    return 0
                
def solution(begin, target, words):
    
    return bfs(begin,target,words)

풀이

begin 단어로 시작해서 words에 있는 단어들을 거쳐서 target 단어를 만드는데 변환이 제일 적은 횟수를 리턴하면 됩니다. 단어가 변환될 때는 알파벳 하나만 바뀐다는게 뽀인트죠~

dfs 함수를 보시면 begin과 target가 같은 경우 변환 횟수를 int형 vector에 넣어두고 재귀를 종료합니다

d가 words의 크기와 같은 경우에도 종료하는데 이는 words의 모든 단어를 다 거쳤는데도 단어가 변환이 안된다는 뜻이여서 값을 넣지 않고 재귀를 종료하는거져

그다음엔 보통 dfs랑 동일합니다~