43163: 단어 변환[DFS/BFS]

Link : programmers.co.kr/learn/courses/30/lessons/43163

---

1. 문제

• 두 개의 단어 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 함수를 작성해주세요.

 

---

2. 문제의 조건

• 주어진 문자는 소문자
• 3 <= 각 단어의 길이 <= 10 모든 단어의 길이는 같다.
• 3 <= 주어지는 단어 <= 50 (중복x)
• begin과 target은 다르다.
• 변활할 수 없으면 0을 반환한다.

 

---

3. 문제 접근

• 시간 복잡도
  
  추후 보강

 

• 아이디어
  
  DFS와 BFS를 하다보면 경험으로 BFS로 접근하면 쉬울 것 같다. 라는 생각할 수 있습니다.
  왜냐하면 hit으로 연관되어있는 부분을 끝까지 탐색하는 것 보다 hit과 비슷한 부분을 전부 탐색하는 것이 더 빠를 것 같은 기분이 들기 떄문입니다.

 

---

4. 풀이 방법

• str1과 str2의 문자열을 비교해주는 함수를 작성합니다.
  해당 문제는 str1과 str2이 한글자만 다르면 바꿀 수 있으므로 그러한 함수를 작성합니다.
• queue를 만들어줍니다. queue에는 처음 begin과 현재의 스택인 0을 입력해줍니다.
• queue가 전부 뽑힐 때 까지 while로 반복합니다.
• 0번째를 항상 뽑아와서 data는 (str, length)가 으로 뽑힐 것입니다.
• 만약 뽑힌 data가 target과 같으면 data[1]인 length를 반환해줍니다.
• 모든 words를 탐색하며 만들어준 함수가 True를 반환한다면 queue에 추가하고 word에서 지워줍니다.
• 만약 queue가 0이 될 때 까지 반환을하지 못하면 찾지 못한 것이므로 문제의 조건에 따라 0을 반환합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/120

 

---

 

cjw.git@gmail.com