프로그래머 / level.3 / 단어 변환(C++)

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

문제 설명

시작과 대상이라는 두 단어와 단어 집합인 단어가 있습니다. 다음 규칙을 사용하여 시작에서 대상까지 가장 짧은 변환 프로세스를 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.

2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 “hit”이고 target이 “cog”이면 단어는 (“hot”,”dot”,”dog”,”lot”,”log”,”cog”) then “hit” -> ” hot” 4단계로 변환할 수 있습니다: ” -> “dot” -> “dog” -> “cog”.

begin과 target이라는 두 단어와 단어의 집합인 words가 매개변수로 주어졌을 때, begin이 target으로 변환될 수 있는지 여부를 적어도 몇 단계를 거쳐 반환하는 솔루션 함수를 작성하십시오.

제한

• 각 단어는 알파벳의 소문자로만 구성됩니다.
• 각 단어의 길이는 3에서 10 사이이며 모든 단어의 길이는 동일합니다.
• 단어는 3개 이상 50개 이하의 단어로 구성되며 겹치는 단어는 없습니다.
• 시작과 대상은 동일하지 않습니다.
• 변환이 불가능하면 0을 반환합니다.

I/O 예시

I/O 예제 설명

예 #1

문제의 예와 동일합니다.

예 #2

대상 “cog”는 단어 내부에 없기 때문에 변환할 수 없습니다.

내 대답

#include <string>
#include <vector>
#include <queue>

using namespace std;

int answer = 0;
vector<bool> checked(50, false);

void DFS(int count, const string& cur, const string& target, const vector<string>& words)
{
    for(int i= 0; i< words.size(); ++i)
    {
        int diffCount = 0;
        
        // words를 탐색하며 단계를 거치지 않은 곳 중
        for(int j = 0; j < words(i).size(); ++j)
        {
            if(cur(j) != words(i)(j))
            {
               if(!checked(i))
                   ++diffCount;
            }
        }
        
        // cur과 다른 문자가 1개 존재한다면 (한번에 하나의 문자만 바꿀 수 있기 때문)
        if(1 == diffCount)
        {
            // 타겟 문자열과 같다면 종료
            if(words(i) == target)
            {
                answer = count+1;
                return;
            }
            
            // 타겟 문자열과 다르다면 words(i) 단계를 거친 뒤
            // 현재 문자열을 words(i)로 설정해 계속 탐색
            else
            {
                checked(i) = true;
                DFS(count+1, words(i), target, words);
            }
        }
        
        // cur과 다른 문자가 1개가 아니라면 계속 탐색한다.
    }
}

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

처음에는 이 문제를 DFS로 해결할 수 있는 이유를 이해하지 못했습니다.

그래서 풀서치로 문제를 풀려고 했으나 테스트 케이스 1~3개에서 계속 문제가 틀렸다.

문제를 다시 보니 단어의 문자열 순서대로 단계를 거치는 것이 아니었습니다!!

2. words에 있는 단어로만 변환할 수 있습니다.

즉, 현재 문자열과 다르고 단어로 문자열 중 방문하지 않은 문자열을 방문, 방문, 방문하면서 가장 빨리 대상 문자열에만 도달하는 것이 문제였습니다!

결국 DFS를 사용하여 아래 그래프를 탐색하면서 Target과 같은 문자에 가장 빨리 도달하는 단계 수를 찾을 수 있습니다.