프로그래머스 단어변환

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

프로그래머스

 

코드

#include <bits/stdc++.h>

using namespace std;
int visited[14];
bool oncheck(string s1, string s2){
    int cnt=0;
    for(int i=0;i<s1.size();i++){
        if(s1[i]!=s2[i]) cnt++; //문자 다른거 개수 세기
    }
    if(cnt==1) return true;
    else return false;
}


int solution(string begin, string target, vector<string> words) {
    int answer = 0; int num=0;
    //1. bfs수행
    queue<pair<string,int>> q;
    q.push({begin,0});
    string s=""; int idx=0;
    while(q.size()){
        tie(s,idx)=q.front(); q.pop();
        if(s==target){
          answer=visited[idx]; break;  
        } 
        for(int i=0;i<words.size();i++){
            if(visited[i]) continue; //방문했다면 continue
            
            if(oncheck(s,words[i])){ //현재 문자랑 word 문자랑 1 차이나면
                visited[i]=visited[idx]+1; //방문표시
                q.push({words[i],i});
            }
        }
        
    }
    
    return answer;
}

 

 

dfs로 수행하다가 최소 단어 변환 수를 보고 bfs로 바꿔야했다.

1차이 나는거를 어떻게 구현할까 고민하다가 답을 봤는데 따로 함수로 빼면 쉬웠다.

1차이 난다 != 같은것이 1개이다 인데 계속 이렇게 생각했었다.

1차이 난다 == 다른것이 1개이다.

 

참고 풀이: 김영진님 풀이 https://school.programmers.co.kr/learn/courses/30/lessons/43163/solution_groups

프로그래머스