[Unsolved][C++] 프로그래머스 단어 변환

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

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

 

1. 서론

 

dfs 문제라고 해서 풀었는데... 뭔가 풀이 방법을 못 찾겠어서 인터넷을 뒤져보니 dfs 백트래킹 문제란다. 쉽지 않다... 백트래킹이 정확하게 뭔지 알려준 문제. 내가 고민하던 부분을 시원하게 긁어줌! 그러고 level 3문제다.

 

2. 문제 풀이

 

words라는 단어의 배열이 주어진다. 그리고 begin과 target이라는 단어가 주어지는데 begin이란 단어에서 시작해서 target이란 단어가 될 때까지 단어를 변환하는데 최소 몇 단계가 걸리는지를 알아내는 문제이다. 변환 과정에는 두 가지 규칙이 있다. 한 번에 한 개의 알파벳만 바꿀 수 있다는 것과 words 배열에 있는 단어로만 변환할 수 있다는 것.

 

처음에 생각했던 것은 words 배열에서 begin과 한 글자만 다른 단어를 찾는다. 그리고 나서 만약 방문하지 않았다면 그 단어가 target과 한 글자라도 일치하는 지를 찾는다. 왜냐하면 target과 상관 없는데 변환하면 소용이 없으니까... 그리고 그걸 target이 나올 때까지 반복했다. 당연히 문제는 안 풀렸다. target까지 가기는 갔지만 가지치기가 제대로 안 된 것이다... 그래서 인터넷을 찾아보니 그 가지치기하는 법이 백트래킹이었다.

 

https://velog.io/@euneun/프로그래머스-단어-변환 BFSDFS-C-v5 lnyekn

[프로그래머스] 단어 변환(BFS,DFS,백트래킹) / C++

 

다른 블로그도 봤지만 이 블로그가 내가 생각했던 것과 가장 근접한 풀이법이었고 설명도 너무 친절해서 이해하기 쉬웠다!!

(감사합니다. 당신의 지식에 감탄합니다!!)

백트래킹의 포인트는 '방문 해제'이다. 최소 경로를 찾기 위해 왔던 길을 되돌아 갈림길에서 다시 탐색을 시작하는 것!!

 

visit [i] = true;

dfs(...);

visit[i] = false;

 

이런 식으로 방문 표시를 하고 다녀온 후에 다시 방문 해제를 해서 다음 분기점에서 다시 탐색을 할 수 있게 해주는 것이다.

이외에는 내가 생각했던 방식과 비슷했다. 이 블로그에서는 따로 함수로 만들어서 처리해줬지만 나는 그냥 dfs 함수 안에서 카운트해서 1개만 다른 값이 있는 걸 찾아줬다. 그리고 하나씩 +1 하면서 배열을 탐색하면서 answer 값을 저장해뒀다가 돌아왔을 때 min 함수를 써서 최소 값인가 아닌가를 판별하고 최소 경로의 수를 구하는 것이다.

 

3. 코드 설명

 

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

using namespace std;

int visit[50];
int answer = 50;

void dfs(vector<string> words, string begin, string target, int start)
{
    if (begin == target)
    {
        answer = min(answer,start);
        return;
    }
    
    for (int i = 0; i < words.size(); i++)
    {
        int cnt = 0;
        for(int j = 0; j < words[i].size(); j++)
            if (words[i][j] != begin[j])
                cnt++;
                    
        if (cnt == 1 && !visit[i])
        {
            visit[i] = true;
            dfs(words, words[i], target, start + 1);
            visit[i] = false;   
        } 
    }  
}

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

    auto it = find(words.begin(), words.end(), target);
    if (it == words.end())
        return 0;
    
    dfs(words, begin, target, 0);
    
    return answer;
}

 

문제에서 변환할 수 없는 경우에는 0을 return 하라고 했기 때문에 target이 있는지 없는지 find함수로 찾고 없는 경우 0을 return 해준다.

그리고 dfs 함수로 들어가 탐색을 시작한다. 배열의 첫 번째 값부터 탐색을 시작하는데 cnt로 단어 중 몇 개의 알파벳이 일치하는지를 보고 1개인 경우에만 방문했다고 표시하고 다시 재귀해서 탐색을 시작한다. 그리고 탐색이 끝나고 돌아오면 방문을 해제해 최소 경로를 구하게 되는 것이다. (min함수 사용) 함수의 종료 조건은 begin값이 target인 경우 값을 구한 것이므로 return 한다.