프로그래머스 C++ 문제 풀이 - 단어 변환(BFS/DFS)

문제 링크

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

프로그래머스

 

생각의 흐름

1. 시작 단어에서 목표 단어까지 변환 시키는 게 배열에 존재하는 변환 가능한 단어를 하나씩 전부 확인해서 목표까지 가야한다. -> 하나씩 전부 확인해야 하니까 BFS를 써보자!
2. 단어 변환이 가능한지 비교하는 함수가 필요하다. 문자열의 i번째 문자를 비교해서 다른 글자 수가 몇개인지 판단해 1개인 경우에만 true를 반환하는 함수를 작성하자!
3. 방문 여부를 검사하고 현재 단어까지 오게 된 수를 기록하기 위해서 map을 사용하자!

 

코드로 구현

bool check(string a, string b){
    int cnt = 0;
    
    for(int i = 0; i < a.size(); ++i){
        cnt += a[i] != b[i] ? 1 : 0;
    }
    
    return cnt == 1 ? true : false;
}

위 함수는 두 문자열을 비교하여 다른 글자가 몇개인지 센 후, 1개인 경우에만 true를 리턴한다.

 

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    map<string, int> m;
    bool haveTarget = false;
    
    for(const auto& s : words){
        m[s] = 0;
        if(s == target) haveTarget = true;
    }
    
    queue<string> q;
    
    q.push(begin);
    m[begin] = 0;
    
    
    while(!q.empty() && haveTarget){
        string cur = q.front();
        if(cur == target){
            answer = m[cur];
            break;
        }
        
        q.pop();
        for(const auto& s : words){
            if(check(s, cur) && m[s] == 0){
                q.push(s);
                m[s] = m[cur] + 1;
            }
        }
    }
    
    
    return answer;
}

방문 여부와 현재 변환 횟수를 저장하기 위한 m을 생성할 때, 만약 words 안에 target이 없다면 while문이 실행되지 않고 종료되도록 하였다. 

 

BFS를 사용하여 begin에서 시작한다. (begin은 방문했지만 변환 횟수가 없으므로 0으로 시작한다.)

문자열을 하나씩 큐에서 꺼내서 목표 문자열인지 확인한다.

만약 목표 문자열이라면 맵에 저장된 변환 횟수를 answer에 담아 리턴한다.

 

아니라면, 범위 기반 for문으로 문자열을 하나씩 꺼내서 변환 가능한 문자열인지 확인하고, 방문하지 않은 문자열인지 확인한다.

 

조건에 맞으면 큐에 집어넣고, 맵에 변환 횟수를 기록한다.

 

반복한다.

 

결과