프로그래머스 - 단어 변환 (C++)

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

프로그래머스

 

dfs/bfs 문제라는 것을 확인했기 때문에 쉽게 풀 수 있었다. 

난 bfs방식을 택했다.

중요한 것은 하나의 단어에 도달하면 다른 단어들은 이 단어에 도달할 수 있어도 할 필요가 없음을 인지해야한다. 만약 지금 이 단어에 도달했는데, 다음으로 이 단어에 도달한다는 것은 결국 최단거리가 아니라는 의미이기 때문이다.

 

그러므로 방문표시를 하고 bfs 탐색을 하면 문제는 풀린다.

 

이 문제가 레벨3인 이유는 아무래도 이것을 dfs/dfs임을 판단하는 것 자체가 실력이라고 생각하는데 이럴거면 분류를 알려주지 않았어야한다고 생각한다.

 

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

bool visited[51] = { false, };

bool check(string a, string b){
    int cnt = 0;
    for(int i = 0; i < a.size(); i++){
        if(a[i] == b[i]) cnt++;
    }

    if(cnt == a.size() - 1) return true;
    else return false;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    queue<pair<string, int>> q;
    
    q.push({begin, 0});
    
    while(!q.empty()){
        string now = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if(now == target){
            answer = cnt;
            break;
        }
        
        for(int i = 0; i < words.size(); i++){
            if(visited[i] == false && check(now, words[i])){
               // cout << now << " " << words[i] << endl;
                q.push({words[i], cnt + 1});
                visited[i] = true;
            }
        }
    }
    
    return answer;
}