[프로그래머스 - 탐색] 단어 변환

카테고리 (Category)	작성 날짜 (Write Date)	최근 수정 날자 (Recent Write Date)	작성자 (Writer)
Algorithm	2021.05.06. 21:52:37	2021.05.06. 21:53:04	Dev.Yang

 

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

 

📄 [탐색] 단어 변환 for Swift Source Code

import Foundation

func difference(left: String, right: String) -> Int {
    
    var result: Int = Int.zero
    
    // MARK: - 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
    for index in left.indices where left[index] != right[index] { result += 1 }
    
    return result
}

func findMinimumChangeLetter(answer: inout Int,
                             visit: inout [String: Bool],
                             word: [String],
                             count: Int, index: String,
                             begin: String, target: String) {
    
    if begin.elementsEqual(target) {
        answer = min(answer, count)
        return
    }
    
    for item in word {
        let differenceWord: Int = difference(left: begin, right: item)
        
        if visit[item] == false && differenceWord == 1 {
            visit[index] = true
            findMinimumChangeLetter(answer: &answer, visit: &visit, word: word,
                                    count: count + 1, index: item,
                                    begin: item, target: target)
        }
    }
}

/**
    1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
    2. words에 있는 단어로만 변환할 수 있습니다.
*/
func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    
    var result: Int = Int.max
    
    // MARK: - 각 단어는 알파벳 소문자로만 이루어져 있습니다.
    guard words.contains(target) else { return Int.zero }
    
    var visit: [String: Bool] = [:]
    var firstIndex: String = String.init()
    
    words.forEach { item in
        visit[item] = false
        
        if difference(left: item, right: begin) == 1 { firstIndex = item }
    }
    
    findMinimumChangeLetter(answer: &result, visit: &visit, word: words,
                            count: Int.zero, index: firstIndex,
                            begin: begin, target: target)
    
    // MARK: - begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾습니다.
    return result
}

---

📄 [탐색] 단어 변환 for C++ Source Code

#include <string>
#include <vector>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;

bool checkGapWord(const string comp, const string target) {
	int gap = 0;
	for (int ii = 0; ii < comp.size(); ii++) { if (comp[ii] != target[ii]) { gap++; } }
	return (gap == 1 ? true : false);
}

void reculsiveDFS(int & answer, string begin, int count, const string target, const vector<string> words, vector<bool> & visit) {

	// Case Find Target.
	if (target == begin) { answer = min(answer, count); return; }

	for (int ii = 0; ii < words.size(); ii++) {
        
        // Case Not Used Word
        if (visit[ii] && checkGapWord(begin, words[ii])) {
            visit[ii] = false; // Used Word
            reculsiveDFS(answer, words[ii], count + 1, target, words, visit);
            visit[ii] = true;  // Unused Word
        }
	}
}

int solution(string begin, string target, vector<string> words) {
	
	int answer = INT_MAX;
    
    vector<bool> visit = vector<bool>(words.size(), true);
	reculsiveDFS(answer, begin, 0, target, words, visit);   

    // 변환할 수 없는 경우에는 0를 return 합니다. (return 0)
	return (answer == INT_MAX ? 0 : answer);
}

---

🚀 REFERENCE

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

ChangYeop-Yang/Study-Algorithm