[프로그래머스/C++] 단어 변환 (DFS 문제 연습)

단어 변환

문제 설명

두 개의 단어 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 합니다.

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

 

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

---

해당 문제는 DFS를 활용한 알고리즘 문제이다.

문제의 핵심은 begin 단어 중에 한 개의 알파벳을 바꿀 때, words 단어 배열에 포함되는 단어가 있는지를 검사하는 과정을 얼마나 효율적으로 작성하는가 인 것 같다.

 

처음 생각한 방법은 다음과 같았다.

1️⃣ 알파벳을 하나씩 치환해서 비교하기

for (int i = 0; i < begin.size(); i++)
{
    if (fixSpel[i]) continue;

    for (int j = 0; j < words.size(); j++)
    {
        string temp = begin.substr(0, i) + words[j][i] + begin.substr(i + 1, begin.size());

        int findIdx = find(words.begin(), words.end(), temp) - words.begin();

        if (!checkUse[findIdx] && findIdx != words.size())
        {
            checkUse[findIdx] = true;
            CheckFixSpelling(words[findIdx], target);

            DFS(words[findIdx], target, words, findCnt+1);

            checkUse[findIdx] = false;
        }
    }
}

 

hit 라는 단어가 있다면, 해당 단어의 길이만큼 for문을 돌면서, words 배열에 있는 단어를 조합하는 것이다.

hit는 _it, h_t, hi_ 의 순서로 알파벳을 변경할 수 있고, words 배열에 "dot", "lot", "cog"가 존재한다면, _it의 조합은 dit, lit, cit가 나오는 것이다.

이렇게 조합된 단어를 words 배열에서 find 함수로 검색하여 존재하는 단어인지를 찾았다.

 

그러나 이러한 방법은 모든 알파벳을 words 배열의 원소와 비교하고, 또 words 배열에 포함되었는지를 비교해야 해서 복잡한 과정과 오랜 시간을 투자해야 한다.

 

따라서 두번째로 생각해낸 방법은 비교하는 단어와 words 배열안에 있는 원소들이 다른 알파벳이 두 개 이상 존재하는지를 검사하는 방법이다.

2️⃣ 알파벳이 두 개 이상 다른지 검사하기

bool CheckIncludeWords(const string str1, const string str2)
{
	int cnt = 0;
	for(int i = 0; i < str1.size(); i++)
	{
		if (str1[i] != str2[i])
			cnt++;
		if (cnt > 1)
			return false;
	}
	return cnt > 1 ? false : true;
}

 

비교단어 두 개의 string을 받아와서, 서로 다른 알파벳이 2개 이상 존재할때는 바로 false를 반환하여 Words 배열에 포함되지 않은 단어임을 알려주었다.

 

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

using namespace std;

bool checkUse[51];
int result = 100;

bool CheckIncludeWords(const string str1, const string str2)
{
	int cnt = 0;
	for(int i = 0; i < str1.size(); i++)
	{
		if (str1[i] != str2[i])
			cnt++;
		if (cnt > 1)
			return false;
	}
	return cnt > 1 ? false : true;
}

void DFS(string& begin, const string target, vector<string>& words, int findCnt)
{
	if (begin == target)
	{
		result = min(result, findCnt);
		return;
	}
	
	for (int i = 0; i < words.size(); i++)
	{
		if (checkUse[i]) continue;

		if(CheckIncludeWords(begin, words[i]))
		{
			checkUse[i] = true;
			DFS(words[i], target, words, findCnt + 1);
			checkUse[i] = false;
		}
	}
}

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

	if (find(words.begin(), words.end(), target) == words.end())
		return 0;

	DFS(begin, target, words, 0);

	return result;
}

 

최종 풀이는 위와 같은 소스코드를 작성하여 제출하였고, 풀이과정은 다음과 같다.

 

1. 시작하는 단어 begin부터 words 배열을 순회하면서 자릿수 하나만 다른 단어가 있는지를 검사한다.

2. 자릿수 하나만 다른 단어가 존재한다면, 해당 단어를 begin으로 DFS를 한번 더 실행한다.

3. 이때, words 배열에서 검사를 수행했는지 여부를 검사하기 위해 bool 배열 checkUse 변수를 사용하였다.

 

사실, words 배열속에 단어를 찾는 과정만 구현하면 매우매우 간단하고 기본적인 DFS인데, 처음에 복잡한  방법으로 단어를 비교하느라 시간을 많이 소모하게 된 것 같아 아쉽다.

좀 더 성장해야 겠다.

---

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=cpp 

프로그래머스