[프로그래머스] DFS/백트래킹 단어 변환 🎯

문제 링크

문제 접근

• 하나의 줄기씩 한 방향으로 갈 수 있을 때까지 탐색해나가므로 dfs 풀이법을 떠올릴 수 있다.

• 변환 단계의 최소값이므로 한번 사용한 단어는 재사용하지 않는 것이 암묵적인 규칙임을 알 수 있다.

• 따라서 단어별로 방문여부를 체크할 배열이 필요하다.

• 탐색함수를 재귀적으로 호출해나가면서 target 단어와 같아졌을때는 함수호출을 종료하는 종료조건을 염두해둔다.

• 문제에서 한 번에 한 개의 알파벳만 바꿀 수 있다고 하였다. 따라서 하나의 줄기씩 탐색을 해나갈때 words 벡터에서 현재의 단어와 한글자만 다른 단어만이 탐색 후보가 될 수 있으므로 다른 문자가 한개인지 판별하는 함수도 작성해야한다.

• dfs를 구현하기 위해 재귀함수를 작성할 때 주의해야할 점은 target문자열과 동일하게 변환이 완료되어 재귀 호출이 종료되었을 경우, 다른 최소경로의 변환과정이 있을 수 있으므로 해당 탐색과정에서 다시 가장 가까운 갈림길로 돌아와서 (back-tracking) 이곳부터 다른 방향으로 다시 탐색을 진행해야 한다는 것이다.

의사 코드

for(int i=0; i<words.size(); i++){
	if(한 개의 문자만 다르다 && 탐색하지 않은 단어다){
    	1. 방문 표시
        visited[i] = true;
        
        2. 그 단어부터 탐색을 다시 시작하기 위해 
        재귀적으로 함수를 호출. 
        dfs(..., step+_1);
        
        3. dfs 재귀 호출하여 종료되어 여기로 돌아오면, 
        백트래킹(원상복구;방문표시해제)하여 
        다음분기점부터 다시 탐색 시작
        visited[i] = false;
    }
}

전체 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int answer = 50; // words 배열은 50개 이하의 단어로 이루어져있다고 하였으므로 단어의 변환 과정은 최대 50단계일 것이다. 
bool visited[50];

// 다른 문자가 1개인지 확인하는 함수
bool checkDiff(string a, string b){
    int dif_cnt = 0;
    for(int i=0; i<a.size(); i++){
        if(a[i] != b[i]){
            dif_cnt++;
        }
    }
    // 다른 문자가 1개일 때
    if(dif_cnt == 1){
        return true;
    }
    // 다른 문자가 1개가 아닐 때
    return false;
}

void dfs(string begin, string target, vector<string> &words, int step){
    // step 이 이전에 찾은 answer 보다 크면 탐색할 필요가 없다
    if(answer <= step) return;
    
    if(begin == target){
        answer = min(answer, step); // 갱신해나가면 answer는 항상 최소값을 유지
        return;
    }
    
    for(int i=0; i<words.size(); i++){
        // 한개의 문자만 다르고 방문하지 않은 단어이면 탐색시작
        if(checkDiff(begin, words[i]) && !visited[i]){
            visited[i] = true;
            // 그 단어부터 탐색을 다시 시작한다. 단계가 하나 추가되었으므로 step+1을 인자로 넘긴다.
            dfs(words[i], target, words, step+1);
            // dfs 재귀 호출하여 종료되어 여기로 돌아오면, 백트래킹하여 다음분기점부터 다시 탐색
            visited[i] = false;
        }
    }
    return;
}


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

    // 탐색 후 target 문자열을 만나지 못했을 때
    if(answer == 50) return 0;

    return answer;
}