728x90
반응형
문제:
두 개의 단어 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 함수를 작성해주세요.
풀이 방법:
깊이/너비 우선 탐색(DFS/BFS) 중 너비 우선 탐색을 사용하는 문제이다. begin에서 변환 할 수 있는 경우의 수를 만들어 주고 이 중에서 target이 있는지 확인한다. 없다면 이 경우의 수를 누적하여 다음 단계를 진행한다. 즉 1단계에서 만들어질수 있는 모든 경우, 2단계에서 만들어지는 경우..가 되는 것이다. 어짜피 target이 있는 층만 알면 되기에 문제 없다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | def solution(begin,target,words): answer=[begin] if target not in words: return 0 answer_count=0 while(len(words)!=0): for i in answer: temp=[] for word in words: count=0 for j in range(len(i)): if i[j]!=word[j]: count+=1 if count==2: break if count==1: temp.append(word) words.remove(word) answer_count+=1 if target in temp: return answer_count else: answer=temp return 0 | cs |
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 2. 점프와 순간이동 (0) | 2019.03.27 |
|---|---|
| [Programmers]Lv 2.소수 만들기 (0) | 2019.03.26 |
| [Programmers]Lv 2. N개의 최소공배수 (0) | 2019.03.24 |
| [Programmers]Lv 3. 숫자 게임 (0) | 2019.03.23 |
| [Programmers]Lv 2.JadenCase 문자열 만들기 (0) | 2019.03.22 |