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 합니다.

입출력 예

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 안에 없기 때문에 변환할 수 없습니다.

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

💻 Javascript 코드

function solution(begin, target, words) {
  let answer = 0;
  let route = [];
  let height = 0;

  const possibleChange = (str) => {
    route.push(str);
    height++;

    const arr = str.split(""); // 'h', 'i', 't'
    const target_arr = target.split("");

    let check = 0;
    for (const i in arr) {
      if (arr[i] !== target_arr[i]) check++;
    }
    if (check !== 1) {
      words.forEach((word) => {
        const tmp = word.split("");
        let check = 0;
        for (const i in tmp) {
          if (tmp[i] !== arr[i]) check++;
        }
        if (check === 1 && !route.includes(word)) {
          possibleChange(word);
        }
      });
    }

    if (answer === 0) {
      answer = height;
    } else {
      height < answer ? (answer = height) : "";
    }
  };
  if (words.includes(target)) {
    possibleChange(begin);
  }
  return answer;
}

💻 Python 코드

def isOneWordDifferent(word1, word2) :
    num_of_different_word = 0
    for a, b in zip(word1, word2) :
        if a != b :
            num_of_different_word += 1
    if num_of_different_word == 1 :
        return True
    else :
        return False
def dfs(begin, path, words, target, paths_length) :
    if begin == target :
        paths_length.append(len(path)-1)
    for w in words :
        if isOneWordDifferent(begin, w) :
            copy_path = path[:]
            copy_path.append(w)
            copy_words = words[:]
            copy_words.remove(w)
            dfs(w, copy_path, copy_words, target, paths_length)
def solution(begin, target, words):
    # 변환할 수 없는 경우
    if target not in words :
        return 0
    path = [begin]
    paths_length = []
    dfs(begin, path, words, target, paths_length)
    
    return min(paths_length)

💡 문제 해결 방법

dfs를 통해 해결하였으며, javascript와 달리 python으로 풀 때는 긴 코드를 함수로 분리하였다. 요즘 함수를 분리하는 연습을 종종하고 있는데 훨씬 코드가 간결해져서 보기에도 좋은 것 같다.

• 변환이 불가능한 경우를 우선적으로 예외처리 한다.
• isOneWordDifferent()함수를 통해 파라미터로 들어오는 두 개의 단어가 서로 하나의 알파벳만 다른지(교체가 가능한지) 확인한다.
• 가능하다면 path에 추가한 후 다시 dfs()로 들어간다.
• target단어에 도착했을 때 path의 길이를 paths_length에 추가한다.
• 모든 탐색(?)이 끝난 후 paths_length 중 가장 작은 값을 return한다.

사실, 아직 dfs의 사용법을 정확하게 모르겠다. 비슷한 코드더라도 변경된 변수를 파라미터로 넣느냐 변수의 복사본을 변경하여 넣느냐로 완전히 코드의 흐름이 갈린다. 최대한 빨리 dfs의 흐름에 대해 공부해야겠다. 왜냐면,,,,,,dfs는,,,,,,코딩테스트에 많이 나오니깐 ㅜ