[L3] 프로그래머스 단어 변환 C++ 백트래킹, 완전 탐색

리뷰

프로그래머스

 

시작 단어에서 한 번에 한 개의 알파벳만 바꿔 words에 있는 단어와 교체하여 목표 단어로 변경하는 문제

백트래킹을 통한 완전 탐색으로 적절한 가지치기를 해가며 재귀를 실행하면 된다.

 

 

전역 변수

• n, len, ans : 입력되는 문자의 길이 n, words벡터의 길이 len, 정답을 저장할 변수 ans
• v : 이미 변경한 단어에 방문 처리를 하기 위한 정수형 변수, 벡터의 최대 길이 50으로 크기를 초기화한다.

 

함수

1. bt

void bt(int level, string begin, const string& target, const vector<string> words)

 

재귀를 진행하며 being에서 target으로 도달할때 까지 완전 탐색을 하는 함수

1. 매개변수로 재귀 단계인 level, 시작 단어인 begin, 목표 단어인 target, 단어 목록 words를 받는다.
2. 기저조건은 두개가 존재한다 먼저 ans가 level보다 작거나 같으면 더 이상 탐색할 필요 없이 리턴한다.
3. begin이 target이 되었을 때 level과 ans를 비교하여 더 적은 값으로 ans를 최신화 하고 리턴한다.
4. words벡터를 순회하며 방문 처리가 되어 있다면 continue처리를 해준다.
5. cnt에 현재 단어와 words단어의 틀린 개수를 체크 해주고, cnt가 2이상이면 continue처리를 해준다.
6. 위 조건에 해당되지 않으면 방문처리 후 재귀단계를 높히고 begin을 words[i]로 바꾸어 재귀를 진행한다.

 

문제풀이

1. n에 문자의 size를, len에 words벡터의 size를 저장해 준다.
2. 만약 words에 target이 존재하지 않으면 탐색을 진행하지 않고 0을 리턴한다.
3. bt를 실행해서 ans값을 최신화 해주고 ans를 리턴해 준다.

 

참고 사항

적절한 가지치기를 해주면 시간 제한은 걱정할 필요가 없다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n, len, ans = 1e9;
int v[50];

void bt(int level, string begin, const string& target, const vector<string> words) {
    if (ans <= level) return;
    if (begin == target) {
        ans = min(ans, level);
        return;
    }
    
    for (int i = 0; i < len; i++) {
        if (v[i]) continue;
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (begin[j] != words[i][j]) cnt++;
        }
        if (cnt > 1) continue;
        v[i] = 1;
        bt(level + 1, words[i], target, words);
        v[i] = 0;
    }
}

int solution(string begin, string target, vector<string> words) {
    n = begin.size();
    len = words.size();
    if (find(words.begin(), words.end(), target) == words.end()) return 0;
    bt(0, begin, target, words);
    
    return ans;
}