단어 변환

Problem. 단어 변환

---

Link.

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

프로그래머스

---

Description.

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

입출력 예시

---

Approach. 

1) 예외처리

• 배열 words 요소중 target이 없는 경우 0을 반환

if(words.filter((el) => el === target).length === 0)
        return 0;

 

2) check 함수 정의

• (규칙#1 만족여부 판단) 현재 문자열과 Candidate 문자열를 비교하여 변환 가능 여부를 판단 (가능: true, 불가능: false 반환)

const check = (original, compare) => {
	let cnt = 0;
    let result = false;
    let len = original.length;
    
    for(let i = 0; i < len; i++) {
        // 현재 문자열(original)과 candidate(compare) 문자열이 중복되는 개수를 count
    	if(original[i] === compare[i])
        	cnt++;
    }
    // 두 문자열이 1개를 제외하고 모두 중복되면
    // 규칙#1 만족 (true)
    if(cnt === len - 1) 
    	result = true;
        
    return result;
}

 

3) DFS 함수 정의

• 규칙 조건에 만족하는 경우를 따라 경우의 수를 하나하나씩 따지는 함수

 

Step#1. 현재 탐색 종료조건 - 1 (solution을 찾은 경우)

• 현재 문자열이 target 문자열과 같은 경우 cnt를 answer 배열에 저장하고 탐색 종료

// 만약 현재 문자열과 target 문자열이 같으면
// result 배열에 cnt를 저장
// 다음 경우의 수를 찾는다 (return)
if(presentBegin === target) {
	answer.push(cnt);
    return;
}

 

 

Step#2. 현재 탐색 종료조건 - 2 (모든 경우의 수를 고려한 경우)

• 현재 경로로 모든 경우의 수를 고려한 경우 탐색 종료

// true: 경우의 수를 고려함 (경로 탐색 O)
// false: 경우의 수를 고려하지 않음 (경로 탐색 X)
let list = isVisited.map((el, idx) => {
if(el === false) return idx;
}).filter((el) => el !== undefined);

// 더이상 탐색할 경로가 없는 경우, 탐색 종료
if(list.length === 0) return;

 

Step#3. 경로 탐색

• 탐색하지 않은 경로를 하나하나씩 탐색

// 탐색하지 않은 문자열의 index를 담은 배열 list
for(let i = 0; i < list.length; i++) {
	let copy = isVisited.slice();
    let index = list[i];
    let nextWord = words[index];
    
    // 현재 문자열에서 다음 문자열 변환 가능한지 체크
   	let isValid = check(presentBegin, nextWord);
    
    // 변환 가능한 경우
    // 해당 경로로 탐색 진행
    if(isValid === true) {
    	let nextBegin = nextWord;
        let copyCnt = cnt + 1;
        let copy = isVisited.slice();
                
        copy[index] = true;
        
        DFS(copy, nextBegin, copyCnt);
    }
}

 

Step#4. DFS 탐색 실행

• 배열 words에 요소들을 차례로 DFS 탐색 시작 (문자열 변환이 가능한 경우만)

 

for(let i = 0; i < words.length; i++) {
	let cnt = 0;
    let nextWord = words[i];
        
    // 현재 문자열에서 다음 문자열 변환 가능한지 체크
    let isValid = check(begin, nextWord);
    
    // 변환 가능한 경우
    // 해당 경로로 DFS 탐색 시작
    if(isValid === true) {
    	let nextBegin = nextWord;
        cnt++;
        let isVisited = new Array(words.length).fill(false);
        
        isVisited[i] = true;
        
        DFS(isVisited, nextBegin, cnt);
    }
}

 

Step#5. 결과 반환

• 만약 배열 answer의 길이가 0이면, 변환할 수 있는 경우의 수가 없다는 의미이기 때문에 0을 반환
• 이외의 경우, 배열내 요소중 최소값을 반환

if(answer.length === 0) 
	return 0;
else 
	return Math.min(...answer);

---

My Answer. 

function solution(begin, target, words) {
    // 예외처리
    // 배열 words 요소중 target이 없는 경우
    // 0을 반환
    if(words.filter((el) => el === target).length === 0)
        return 0;
    
    const check = (original, compare) => {
       
        let cnt = 0;
        let result = false;
        let len = original.length;
        for(let i = 0; i < len; i++) {
            if(original[i] === compare[i])
                cnt++;
        }

        if(cnt === len - 1) 
            result = true;
        
        return result;
    }
    
    const DFS = (isVisited, presentBegin, cnt) => {
        // 만약 현재 문자열과 target 문자열이 같으면
        // result 배열에 cnt를 저장
        // 다음 경우의 수를 찾는다 (return)
        if(presentBegin === target) {
            answer.push(cnt);
            return;
        }
        
        let list = isVisited.map((el, idx) => {
            if(el === false) return idx;
        }).filter((el) => el !== undefined);
        
        if(list.length === 0) return;
        
        for(let i = 0; i < list.length; i++) {
            let copy = isVisited.slice();
            let index = list[i];
            let nextWord = words[index];
            
            // 현재 문자열에서 다음 문자열 변환 가능한지 체크
            let isValid = check(presentBegin, nextWord);
            
            if(isValid === true) {
                let nextBegin = nextWord;
                let copyCnt = cnt + 1;
                let copy = isVisited.slice();
                
                copy[index] = true;
                
                DFS(copy, nextBegin, copyCnt);
            }
        }
        
        return;
    }
    
    let answer = [];
    
    for(let i = 0; i < words.length; i++) {
        
        let cnt = 0;
        let nextWord = words[i];
        
        // 현재 문자열에서 다음 문자열 변환 가능한지 체크
        let isValid = check(begin, nextWord);
        
        if(isValid === true) {
            let nextBegin = nextWord;
            cnt++;
            let isVisited = new Array(words.length).fill(false);
            
            isVisited[i] = true;
            
            DFS(isVisited, nextBegin, cnt);
        }
    }
    
    if(answer.length === 0) 
        return 0;
    else 
        return Math.min(...answer);
}

---

References.

---

For Developer. 

• 잘못되거나 부족한 부분이 있다면 언제든지 댓글 부탁드립니다 :)