단어변환
문제설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
- 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
- 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 합니다.
입출력 예
- 각 단어는 알파벳 소문자로만 이루어져 있습니다.
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
- begin과 target은 같지 않습니다.
- 변환할 수 없는 경우에는 0를 return 합니다.
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.
풀이
해당문제는 전형적인 BFS문제입니다. BFS 문제의 경우 "최단","최소"를 찾는 경우가 많습니다. 문제에서도 단어가 변환되는 최소의 단계를 구하는 것이기 때문에 BFS 알고리즘을 사용하여 풀면 되겠습니다.
BFS 알고리즘의 설명은 아래를 참고하여 주십시오.
https://tylee82.tistory.com/329?category=940295
[JAVA] 너비 우선 탐색 BFS(Breadth-first search)
동작방식 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비
tylee82.tistory.com
이외에도 isCanChange 함수에서 문자1(str1)과 문자2(str2)를 비교해 한개의 알파벳만 변환을 했는지 검사를 하는 함수가 있습니다. 저는 str1과 str2의 문자 하나하나를 char로 변환하여 빼기를 하여 절대값을 해주었습니다. 이렇게하면 문자의 차이가 나오는데 같은 문자라면 '0'이 나타날 것 입니다. '0'이 아닌 위치는 알파벳이 변환이 되었으니 이후에 나오는 알파벳은 모두 '0'이 나와야 한다는 가정으로 새우고 함수를 만들었습니다.
import java.util.*;
class Solution {
class Word{
String str;
int count;
Word(String str, int count){
this.str = str;
this.count = count;
}
}
public boolean isCanChange(String str1, String str2){
//한 번에 한 개의 알파벳만 바꿀 수 있습니다.
boolean ret = false;
int len = str1.length();
boolean isOneChange = false;
int diffWord = 0;
for(int i=0; i<len; i++){
diffWord = Math.abs(str1.charAt(i) - str2.charAt(i));
if(!isOneChange && diffWord != 0) {
isOneChange = true;
ret = true;
}else if(isOneChange && diffWord != 0){
ret = false;
break;
}
}
return ret;
}
public int solution(String begin, String target, String[] words) {
int answer = 0;
int[] used = new int[words.length]; // 사용한것은 1, 안한것은 0
Queue<Word> q = new LinkedList<Word>();
q.add(new Word(begin, 0)); //시작점
while(!q.isEmpty()){
Word cur = q.poll();
if(cur.str.equals(target)){
// terget과 문자가 동일하면 cur.count 반환하고 멈춤
answer = cur.count;
break;
}
for(int i=0; i<words.length; i++){
if(isCanChange(cur.str, words[i] ) && used[i] == 0) //변환이 가능하고 사용하지 않았으면 q에 넣어준다.
{
used[i] = 1; // 방문 표시
q.add(new Word(words[i] , cur.count+1));
}
}
}
return answer;
}
}결과
