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

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
   예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

각 단어는 알파벳 소문자로만 이루어져 있습니다.
각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
begin과 target은 같지 않습니다.
변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

Solution

#include <string>
#include <vector>
#define MAX 50
#define INF 987654321
using namespace std;
bool Visit[50];
int answer = INF;

int cmpString(string A, string B, int N){
    int result = 0;
    for(int i = 0; i < N; i++){
        if(A[i] != B[i]) result++;
    }
    return result;
}
void DFS(string data, string target, vector<string> words, int count){
    if(data == target) {
        answer = min(answer, count);
        return;
    }
    for(int i = 0; i < words.size(); i++){
        if(cmpString(data, words[i], data.length())==1){
            if(!Visit[i]){
                Visit[i] = true;
                DFS(words[i], target, words, count+1);
                Visit[i] = false;}
        }
    }
}

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

우선 어쨌든 한 글자만 다른 지 확인 해 보아야 한다.

int cmpString(string A, string B, int N){
    int result = 0;
    for(int i = 0; i < N; i++){
        if(A[i] != B[i]) result++;
    }
    return result;
}

크게 상관은 없을 지 모르겠다만 문자열의 길이를 패러미터로 받았다. length연산을 그렇게 매번 하진 않을테니 크게 차이는 없지 싶다.
어쨌든 이 함수의 용도는 두 문자열을 비교했을 때 한 글자만 차이나는지를 확인하기 위해서였다.

void DFS(string data, string target, vector<string> words, int count){
    if(data == target) {
        answer = min(answer, count);
        return;
    }
    for(int i = 0; i < words.size(); i++){
        if(cmpString(data, words[i], data.length())==1){
            if(!Visit[i]){
                Visit[i] = true;
                DFS(words[i], target, words, count+1);
                Visit[i] = false;}
        }
    }
}

본격적으로 DFS를 돌린다. 패러미터가 많다. 굳이 저렇게 많이 달거까지 있었나 싶었다. 문제를 너무 무지성으로 풀은 내 잘못이다. 우선 뭐 간단하다 현재 탐색이 진행중인 기준인 data가 target과 같다면? 그러면 정답이니 일단 갱신하는데 왜 min 함수를 사용했는가? 하면 다양한 경우의 수가 나올 수 있기 때문이다.
그래서 일단 answer를 나올 수 없는 큰 수로 설정한 후 계속해서 탐색이 재귀적으로 진행될 때 만약 결론이 나왔다면 탐색횟수값이 최소값이라면 정답에 갱신하는 방식이다.
재귀함수 정도는 이해해야 풀 수 있는 문제다. DFS를 통해 정답을 찾아내는것 까지는 아이디어를 낼 수 있겠지만...아마 재귀함수의 특징을 이해하지 못한다면 어떻게 Count 해야 할 지도 이해가 안되었을 것이라 생각한다.

for(int i = 0; i < words.size(); i++){
    if(cmpString(data, words[i], data.length())==1){
        if(!Visit[i]){
            Visit[i] = true;
            DFS(words[i], target, words, count+1);
            Visit[i] = false;}
    }
}

for문만 다시 보자. 탐색하지 않은 곳을 true 처리하고 재귀적으로 DFS를 돌리는 건 DFS를 구현해본 사람이라면 해 낼수 있는 생각이지만, 재귀함수 하나가 종료되면 다시 해당 인덱스의 방문 기록을 초기화 시킨다. 다양한 경우가 있을 수 있으니까 이런 장치가 필요하다.

충분히 코딩테스트에 나올 법한 어려운 문제였다. DFS를 응용해볼 수 있는 대표적인 문제였다.