[프로그래머스 단어 변환] c++ (풀이, 코드, bfs)

문제 링크

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

프로그래머스

 

문제

 

풀이, 코드

bfs의 문제로 level3이지만 아주 간단한 bfs가 아닐까 생각합니다.

 

우선 둘과의 차이가 1개가 나는것에 대해서(중복이 없으니 0개는 없음)

방문을 하지 않았다면 q.push({cnt + 1,words[i]})를 통해 반복문이 계속 돌아가게 되는 구조 입니다.

 

사실 bfs의 가장 정석적인 문제라 

bfs에 대한 기초적인 방식인

처음에 push를 한다 -> 반복문을 큐가 빌때까지 돈다 -> 원하는 데이터를 뽑아온후 pop을한다 

-> 찾는 데이터가 있다면 return을 한다(그게 아닐시에는 q가 다 비워지며 반복문을 탈출하게 됨)

 

 

/*

단어 변환

한번에 한개의 알파벳만 words에 있는 단어로만 변환 o

최소 몇단계를 과정을 거쳐서 변환할 수 있는지에 대해서 하는 것이니 bfs를 사용해보자.

*/

#include <string>

#include <vector>

#include <queue>

#include <iostream>

using namespace std;

int solution(string begin, string target, vector<string> words) {

    int answer = 0;

    queue<pair<int,string>> q; //횟수, word

   

    int visited[50]={0,};

    q.push({0,begin});

   

    while(!q.empty()){

        int cnt = q.front().first;

        string name = q.front().second;

       

        q.pop();

       

        if(name == target)

            return cnt;

       

        for(int i = 0; i < words.size();i++){

            int diff = 0;

            for(int j = 0; j < name.length();j++){

                if(name[j] != words[i][j])

                    diff++;

            }

            if(diff == 1 && visited[i] == 0){

                visited[i] = 1;

                q.push({cnt + 1,words[i]});

            }

        }

    }

    return answer;

}