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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

 

 

문제 풀이

현재 단어에서 하나의 문자만 다른 단어를 찾아 해당 단어부터 다시 DFS를 거치는 방식으로 풀면 된다.

먼저, 두 단어가 한 가지의 문자만 다른지 찾는 함수를 구현해준다.

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

        if(cnt > 1) return false;
    }

    if(cnt == 1) return true;
    else return false;
}

 

다음으로, DFS를 구현해준다. DFS에 필요한 파라미터는 현재 단어(cur), 타겟 단어(target), 문자열 배열(words), 인덱스(idx)이다. 종료 조건은 현재 단어가 타겟 단어와 동일할 때이고, 이 때 최소 단계수를 계산해준다. 탐색 조건은 문자열 배열을 돌며 방문하지 않았고 앞서 구현한 함수를 만족하는 문자열을 찾아 해당 단어에서 다시 DFS를 거쳐준다. DFS에서 빠져 나왔을 때 visited 배열을 다시 false로 바꿔줘야 다음 탐색에서 사용할 수 있다.

void DFS(string cur, string target, vector<string> words, int idx){
    if(cur == target){
        answer = min(answer, idx);
        return;
    }
    
    for(int i=0; i<words.size(); i++){
        if(!visited[i] && isAbleToChange(cur, words[i])){
            visited[i] = true;
            DFS(words[i], target, words, idx + 1);
            visited[i] = false;
        }
    }
    
    return;
}

 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
bool visited[51] = { false, };
int answer = 50;

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

        if(cnt > 1) return false;
    }

    if(cnt == 1) return true;
    else return false;
}

void DFS(string cur, string target, vector<string> words, int idx){
    if(cur == target){
        answer = min(answer, idx);
        return;
    }
    
    for(int i=0; i<words.size(); i++){
        if(!visited[i] && isAbleToChange(cur, words[i])){
            visited[i] = true;
            DFS(words[i], target, words, idx + 1);
            visited[i] = false;
        }
    }
    
    return;
}

int solution(string begin, string target, vector<string> words) {
    DFS(begin, target, words, 0);
    
    return answer == 50 ? 0 : answer;
}